仅执行一次字符串交换能否使两个字符串相等
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 16.6 MB
/*
* 思路:
* 1. 如果 s1 和 s2 已经相等,直接返回 true。
* 2. 使用 IntStream 找出 s1 和 s2 中不同的字符位置。
* 3. 如果不同的字符位置不是两个,返回 false。
* 4. 检查是否可以通过交换 s1 或 s2 中的两个不同字符使得 s1 和 s2 相等。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean areAlmostEqual(String s1, String s2) {
if (s1.equals(s2)) return true;
int[] diffIndices = IntStream.range(0, s1.length())
.filter(i -> s1.charAt(i) != s2.charAt(i))
.toArray();
if (diffIndices.length != 2) return false;
return s1.charAt(diffIndices[0]) == s2.charAt(diffIndices[1]) && s1.charAt(diffIndices[1]) == s2.charAt(diffIndices[0]);
}
}
解释
方法:
题解的思路是通过一次遍历两个字符串,记录下所有位置上字符不相同的情况。使用两个变量a和b来存储第一次发现的不匹配字符,如果在遍历过程中发现第二对不匹配的字符,会检查这对字符是否能通过一次交换与前一对不匹配的字符匹配(即 s1[i] 应等于之前的 b 且 s2[i] 应等于之前的 a)。如果能够匹配,继续检查是否有更多不匹配,如果有,则直接返回 false。如果整个遍历完成后只发现一对或没有不匹配的字符,返回 true。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到的算法只记录了两个不匹配的字符位置,如果存在多于两处的不匹配但仍然可以通过一次交换解决的情况,该算法是否能正确处理?
▷🦆
为什么在发现第二处不匹配时,就直接使用`(if s1[i] != b or s2[i] != a)`来判断是否可以通过一次交换使两字符串相等?是否有可能出现更复杂的字符交换情况?
▷🦆
题解中在一次遍历中只处理了至多两处不匹配的情况,如果在处理完这两处后仍有其他字符不匹配怎么办?
▷🦆
在题解的逻辑中,当`c != 1`时返回`True`,这是否意味着如果没有不匹配或者有两处不匹配但可以解决则返回`True`?这样的逻辑是否总是准确的?
▷