leetcode
leetcode 1601 ~ 1650
仅执行一次字符串交换能否使两个字符串相等

仅执行一次字符串交换能否使两个字符串相等

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
题解中提到的算法只记录了两个不匹配的字符位置,如果存在多于两处的不匹配但仍然可以通过一次交换解决的情况,该算法是否能正确处理?
该算法不能正确处理存在多于两处不匹配的情况。算法的设计是基于当出现多于两个不匹配的位置时,无法通过一次交换使两个字符串相等的假设。如果真实场景中存在多于两个不匹配但可以通过一次交换解决的情况,该算法会错误地返回 false。
🦆
为什么在发现第二处不匹配时,就直接使用`(if s1[i] != b or s2[i] != a)`来判断是否可以通过一次交换使两字符串相等?是否有可能出现更复杂的字符交换情况?
这种判断是基于两处不匹配且这两处可以通过互换各自的字符来匹配的特殊情况。如果`s1[i]`等于之前的`b`且`s2[i]`等于之前的`a`,则这两个位置的字符完全可以通过一次交换来匹配。该逻辑很简单,且在这个特定场景中有效,不适用于更复杂的交换情况。该算法假设除了这两个不匹配外,其他位置的字符都是匹配的。
🦆
题解中在一次遍历中只处理了至多两处不匹配的情况,如果在处理完这两处后仍有其他字符不匹配怎么办?
根据该算法的设计,如果在处理完这两处不匹配的情况后仍然存在其他不匹配的字符,算法将返回 false。该算法基于的假设是,要么不存在不匹配的字符,要么存在的不匹配可以仅通过一次交换解决。因此,存在更多不匹配的情况不符合算法设计的前提,因此返回 false 是符合逻辑的。
🦆
在题解的逻辑中,当`c != 1`时返回`True`,这是否意味着如果没有不匹配或者有两处不匹配但可以解决则返回`True`?这样的逻辑是否总是准确的?
是的,这种逻辑在假设只有两处或没有不匹配的情况下是准确的。如果`c`的值不是1,意味着没有不匹配的字符或者有两处不匹配的字符且可以通过一次交换解决。这是因为如果有不匹配的字符且无法通过交换解决,`c`将会为1,此时返回 false。因此,这样的逻辑在规定的假设下是有效的。

相关问题