判断两字符串是否仅有一处编辑距离:先检查长度差≤1;等长时允许一位不同;长度差为1时用双指针,较长串跳过一位后剩余字符须完全匹配。

直接比较字符差异位置
核心思路是遍历两个字符串,逐位比对,记录第一个不同位置;继续往后找,如果出现第二个不同位置就立刻返回 false。关键在于提前终止,避免无谓遍历。
需注意:两个字符串长度不同时,差异可能出现在“长度差”本身——比如 "abc" 和 "abcd",本质是末尾多一个字符,也算「一处差异」,但不能靠纯逐位比对发现。
- 先检查长度差是否 ≤ 1,否则直接返回 false
- 若等长,用单指针遍历,最多允许 1 次
str1[i] != str2[i] - 若长度差为 1,用双指针:较长串走一步、较短串停住,之后必须完全匹配
处理插入/删除类差异(长度差为1)
当 abs(len1 - len2) == 1 时,“只有一处差异”实际对应「一次插入」或「一次删除」,二者互为逆操作。此时不能简单跳过某一位再比对剩余——必须保证跳过的那一位之后,其余字符完全一致。
例如 "abc" 和 "ac":在索引 1 处发现 'b' != 'c',此时应假设长串("abc")的 'b' 是多出的,于是跳过它,继续比对 "c" 和 "c" —— 成功。
立即学习“C++免费学习笔记(深入)”;
- 固定让
str1为较长串(可通过交换实现) - 用
i遍历str1,j遍历str2,首次失配时只让i++,j不动 - 之后所有剩余字符必须严格相等,且
i和j最终都走到末尾
边界情况容易漏判
空字符串、单字符、完全相同、仅首尾不同——这些场景下逻辑容易出岔。尤其要注意:两个完全相同的字符串,差异数是 0,不满足「只有一处」;而 "" 和 "a" 是合法的 1 处差异。
-
""vs"a"→ 允许(长度差 1,且无后续字符需比对) -
"a"vs"a"→ 不允许(差异数为 0) -
"ab"vs"ac"→ 允许(等长,仅索引 1 处不同) -
"ab"vs"abc"→ 允许(长度差 1,且"ab"完全匹配"abc"前缀) -
"ab"vs"ade"→ 不允许(长度差 1,但跳过'd'后'e'无法匹配'b')
代码实现要点(C++)
别用 std::string::compare 或 == 一锅端,它们无法暴露差异位置。手写双指针最可控,且能 O(n) 时间内完成。
示例关键逻辑片段:
bool oneEditAway(const string& s1, const string& s2) {
int len1 = s1.length(), len2 = s2.length();
if (abs(len1 - len2) > 1) return false;
if (len1 == len2) {
int diff = 0;
for (int i = 0; i < len1; ++i) {
if (s1[i] != s2[i]) diff++;
if (diff > 1) return false;
}
return diff == 1;
}
// len1 != len2, assume len1 > len2
const string& longer = len1 > len2 ? s1 : s2;
const string& shorter = len1 > len2 ? s2 : s1;
int i = 0, j = 0;
while (i < longer.length() && j < shorter.length()) {
if (longer[i] != shorter[j]) {
if (i != j) return false; // 第二次失配
i++; // 跳过 longer 中的异常字符
continue;
}
i++; j++;
}
return i == longer.length() && j == shorter.length();
}
注意:上面双指针部分中,i != j 是判断是否已跳过一次的关键——因为只有首次失配时 i == j,之后再失配说明跳过无效。
真正难的是把插入、删除、替换三种语义统一到一套分支里,而不是写三段重复逻辑。少一次分支,就少一个漏判点。


















