LeetCode 1790: Check if One String Swap Can Make Strings Equal (Mismatch Pair Validation)
LeetCode 1790StringGreedySimulationToday we solve LeetCode 1790 - Check if One String Swap Can Make Strings Equal.
Source: https://leetcode.com/problems/check-if-one-string-swap-can-make-strings-equal/
English
Problem Summary
Given two strings s1 and s2 of the same length, determine whether you can make them equal by performing at most one swap on exactly one of the strings.
Key Insight
If one swap can fix the strings, there must be either:
1) 0 mismatches (already equal), or
2) exactly 2 mismatches and they must cross-match: s1[i] == s2[j] and s1[j] == s2[i].
Brute Force and Limitations
Trying all possible swaps is O(n^2) candidates and each check may cost O(n), which is unnecessary. We only need to collect mismatch positions once.
Optimal Algorithm Steps
1) Scan both strings and record indices where s1[i] != s2[i].
2) If mismatch count is 0, return true.
3) If mismatch count is not 2, return false.
4) Let mismatches be i and j. Return whether cross-match conditions hold.
Complexity Analysis
Time: O(n).
Space: O(1) (store at most two mismatch indices).
Common Pitfalls
- Forgetting the "already equal" case.
- Accepting 1 mismatch (impossible with one swap).
- Checking only one direction instead of cross-match both ways.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean areAlmostEqual(String s1, String s2) {
int first = -1, second = -1;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
if (first == -1) first = i;
else if (second == -1) second = i;
else return false;
}
}
if (first == -1) return true;
if (second == -1) return false;
return s1.charAt(first) == s2.charAt(second)
&& s1.charAt(second) == s2.charAt(first);
}
}func areAlmostEqual(s1 string, s2 string) bool {
first, second := -1, -1
for i := 0; i < len(s1); i++ {
if s1[i] != s2[i] {
if first == -1 {
first = i
} else if second == -1 {
second = i
} else {
return false
}
}
}
if first == -1 {
return true
}
if second == -1 {
return false
}
return s1[first] == s2[second] && s1[second] == s2[first]
}class Solution {
public:
bool areAlmostEqual(string s1, string s2) {
int first = -1, second = -1;
for (int i = 0; i < (int)s1.size(); i++) {
if (s1[i] != s2[i]) {
if (first == -1) first = i;
else if (second == -1) second = i;
else return false;
}
}
if (first == -1) return true;
if (second == -1) return false;
return s1[first] == s2[second] && s1[second] == s2[first];
}
};class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
diff = []
for i, (a, b) in enumerate(zip(s1, s2)):
if a != b:
diff.append(i)
if len(diff) > 2:
return False
if not diff:
return True
if len(diff) != 2:
return False
i, j = diff
return s1[i] == s2[j] and s1[j] == s2[i]var areAlmostEqual = function(s1, s2) {
let first = -1, second = -1;
for (let i = 0; i < s1.length; i++) {
if (s1[i] !== s2[i]) {
if (first === -1) first = i;
else if (second === -1) second = i;
else return false;
}
}
if (first === -1) return true;
if (second === -1) return false;
return s1[first] === s2[second] && s1[second] === s2[first];
};中文
题目概述
给定两个等长字符串 s1 和 s2，判断是否可以通过在其中一个字符串上进行至多一次交换，使两者相等。
核心思路
一次交换最多修复两个位置，因此只有两种可能：
1）没有不相等位置（本来就相等）；
2）恰好有两个不相等位置，并且这两个位置交叉匹配。
暴力解法与不足
暴力枚举交换对需要 O(n^2)，每次还要比较字符串，整体成本高。其实只需一次线性扫描记录不匹配下标。
最优算法步骤
1）遍历下标，收集 s1[i] != s2[i] 的位置。
2）若不匹配数为 0，返回 true。
3）若不匹配数不是 2，返回 false。
4）设两个位置为 i, j，检查 s1[i] == s2[j] 且 s1[j] == s2[i]。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)（最多存两个下标）。
常见陷阱
- 忽略“原本就相等”的情况。
- 将“1 个不匹配”误判为可交换修复。
- 只检查单向字符相等，漏掉交叉匹配条件。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean areAlmostEqual(String s1, String s2) {
int first = -1, second = -1;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
if (first == -1) first = i;
else if (second == -1) second = i;
else return false;
}
}
if (first == -1) return true;
if (second == -1) return false;
return s1.charAt(first) == s2.charAt(second)
&& s1.charAt(second) == s2.charAt(first);
}
}func areAlmostEqual(s1 string, s2 string) bool {
first, second := -1, -1
for i := 0; i < len(s1); i++ {
if s1[i] != s2[i] {
if first == -1 {
first = i
} else if second == -1 {
second = i
} else {
return false
}
}
}
if first == -1 {
return true
}
if second == -1 {
return false
}
return s1[first] == s2[second] && s1[second] == s2[first]
}class Solution {
public:
bool areAlmostEqual(string s1, string s2) {
int first = -1, second = -1;
for (int i = 0; i < (int)s1.size(); i++) {
if (s1[i] != s2[i]) {
if (first == -1) first = i;
else if (second == -1) second = i;
else return false;
}
}
if (first == -1) return true;
if (second == -1) return false;
return s1[first] == s2[second] && s1[second] == s2[first];
}
};class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
diff = []
for i, (a, b) in enumerate(zip(s1, s2)):
if a != b:
diff.append(i)
if len(diff) > 2:
return False
if not diff:
return True
if len(diff) != 2:
return False
i, j = diff
return s1[i] == s2[j] and s1[j] == s2[i]var areAlmostEqual = function(s1, s2) {
let first = -1, second = -1;
for (let i = 0; i < s1.length; i++) {
if (s1[i] !== s2[i]) {
if (first === -1) first = i;
else if (second === -1) second = i;
else return false;
}
}
if (first === -1) return true;
if (second === -1) return false;
return s1[first] === s2[second] && s1[second] === s2[first];
};
Comments