0161. One Edit Distance¶
题目信息¶
- 题号:
相隔为 1 的编辑距离
- 难度:
Medium
- 主题:
字符串、双指针、编辑距离、分类讨论
- 原题:
- 重点:
用长度差确定唯一可能的编辑类型,在首次不匹配处消费一次机会,并排除零次或两次以上编辑
题目重述¶
给定字符串 s、t,判断能否对其中一个字符串恰好执行一次编辑,使两者相等。一次编辑只能是插入
一个字符、删除一个字符或把一个字符替换成另一个字符。原本相等的字符串编辑距离为零,应返回 false;
需要两次及以上编辑也返回 false。
自建示例¶
s = "ab"、t = "ac":替换b为c,返回true;s = "ab"、t = "acb":在a后插入c,返回true;s = "ab"、t = "ab":无需编辑,不满足“恰好一次”,返回false;s = "ab"、t = "ba":有两个位置不同,一次替换不够,返回false;空串与单字符字符串相隔一次插入,返回
true;两个空串返回false。
C++ 实现¶
#include <string>
class Solution {
private:
bool differByExactlyOneEdit(
const std::string& first,
const std::string& second
) {
if (first.size() > second.size()) {
return differByExactlyOneEdit(second, first);
}
const int shorterLength = static_cast<int>(first.size());
const int longerLength = static_cast<int>(second.size());
if (longerLength - shorterLength > 1) {
return false;
}
int shorterIndex = 0;
int longerIndex = 0;
int editsUsed = 0;
while (shorterIndex < shorterLength &&
longerIndex < longerLength) {
if (first[shorterIndex] == second[longerIndex]) {
++shorterIndex;
++longerIndex;
continue;
}
++editsUsed;
if (editsUsed > 1) {
return false;
}
if (shorterLength == longerLength) {
++shorterIndex;
}
++longerIndex;
}
return editsUsed == 1 ||
longerLength == shorterLength + 1;
}
public:
bool isOneEditDistance(std::string s, std::string t) {
return differByExactlyOneEdit(s, t);
}
};
题解¶
通用编辑距离做了多少多余工作¶
一般编辑距离动态规划要为所有前缀对计算最少操作数,状态量 O(mn);也可以枚举每个位置可能执行的
插入、删除、替换,再比较完整字符串。可是本题只关心距离是否恰好为一,绝大多数状态在第二次不匹配出现后
已经没有继续计算价值。
一次编辑对长度的影响只有 -1、0、+1。因此两串长度差超过一可立即判假;长度相等时唯一可能
是一次替换,长度相差一时唯一可能是对短串插入一个字符,等价地对长串删除一个字符。这个分类把通用三种
选择压缩为由长度决定的唯一推进规则。
先统一谁是短串¶
辅助函数保证 first.size() <= second.size()。若传入顺序相反,只交换参数递归一次;后续便只需讨论
“等长”或“第二串长一”,不用为删除和插入写两套镜像分支。字符串按常量引用传递,交换调用不复制内容。
双指针的不变量¶
循环开始时,两个指针之前的前缀已经通过至多 editsUsed 次编辑对齐。字符相等时,两边同时前进,不消耗
编辑。第一次不同按长度执行:
等长:只能把一个字符替换成另一个,两个指针都前进;
长串多一个字符:把长串当前字符视为需要删除的字符,或视为短串此处缺少的插入字符;只前进长串指针, 短串当前字符留待与下一个字符比较。
第二次不匹配意味着唯一编辑机会已经用完,立即返回 false。两种推进都不会回退,因此此前对齐前缀
不会被重新检查。
具体走读插入情况¶
对 first="ab"、second="acb":
指针字符 |
状态 |
动作 |
|---|---|---|
|
相等, |
两指针都前进 |
|
首次不匹配,长串多一字符 |
只跳过长串 |
|
再次相等 |
两指针前进到末尾,返回真 |
若第二串是 "acd",跳过 c 后还会比较 b 与 d,形成第二次不匹配并返回假。
循环结束后为何还要检查尾部¶
如果扫描中已经遇到一次不匹配,editsUsed == 1 表示那次替换或插入/删除使其余部分对齐,答案为真。
如果一直没有不匹配:
两串等长,说明完全相同,编辑次数为零,必须返回假;
长串恰好多一个字符,额外字符只能在尾部,一次插入/删除即可,必须返回真。
所以返回条件是 editsUsed == 1 或长度恰差一。长度差分支也覆盖空串与单字符字符串。
为什么不能把条件写成“最多一次”¶
许多实现只在发现第二个差异时返回假,最后无条件返回真,会把 "ab" 与 "ab" 误判。题目询问的
不是能否用不超过一次编辑变成相等,而是编辑距离是否等于一;零次状态必须在最终分支明确排除。
正确性与复杂度¶
若算法返回真,等长时记录的唯一不匹配可由一次替换修复;差一时唯一跳过字符或尾部多字符可由一次插入/ 删除修复。反之,任意一次编辑可行的字符串长度差至多一,且除编辑位置外字符顺序完全相同;双指针会在该 位置使用唯一对应推进,此后不会出现第二个差异,所以必返回真。
两个指针最多各扫描一次,时间 O(min(m,n)) 至 O(m+n),额外空间 O(1)。通用编辑距离表没有
提供本题所需之外的认知收益,因此 C++ 只保留长度分类后的双指针主解。