0161. One Edit Distance ======================= 题目信息 -------- :题号: 0161. 相隔为 1 的编辑距离 :难度: Medium :主题: 字符串、双指针、编辑距离、分类讨论 :原题: `LeetCode 0161 `_ :重点: 用长度差确定唯一可能的编辑类型,在首次不匹配处消费一次机会,并排除零次或两次以上编辑 题目重述 -------- 给定字符串 ``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++ 实现 -------- .. code-block:: cpp #include 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(first.size()); const int longerLength = static_cast(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"``: .. list-table:: :header-rows: 1 * - 指针字符 - 状态 - 动作 * - ``a`` 与 ``a`` - 相等,``editsUsed=0`` - 两指针都前进 * - ``b`` 与 ``c`` - 首次不匹配,长串多一字符 - 只跳过长串 ``c``,``editsUsed=1`` * - ``b`` 与 ``b`` - 再次相等 - 两指针前进到末尾,返回真 若第二串是 ``"acd"``,跳过 ``c`` 后还会比较 ``b`` 与 ``d``,形成第二次不匹配并返回假。 循环结束后为何还要检查尾部 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 如果扫描中已经遇到一次不匹配,``editsUsed == 1`` 表示那次替换或插入/删除使其余部分对齐,答案为真。 如果一直没有不匹配: * 两串等长,说明完全相同,编辑次数为零,必须返回假; * 长串恰好多一个字符,额外字符只能在尾部,一次插入/删除即可,必须返回真。 所以返回条件是 ``editsUsed == 1`` 或长度恰差一。长度差分支也覆盖空串与单字符字符串。 为什么不能把条件写成“最多一次” ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 许多实现只在发现第二个差异时返回假,最后无条件返回真,会把 ``"ab"`` 与 ``"ab"`` 误判。题目询问的 不是能否用不超过一次编辑变成相等,而是编辑距离是否等于一;零次状态必须在最终分支明确排除。 正确性与复杂度 ~~~~~~~~~~~~~~ 若算法返回真,等长时记录的唯一不匹配可由一次替换修复;差一时唯一跳过字符或尾部多字符可由一次插入/ 删除修复。反之,任意一次编辑可行的字符串长度差至多一,且除编辑位置外字符顺序完全相同;双指针会在该 位置使用唯一对应推进,此后不会出现第二个差异,所以必返回真。 两个指针最多各扫描一次,时间 ``O(min(m,n))`` 至 ``O(m+n)``,额外空间 ``O(1)``。通用编辑距离表没有 提供本题所需之外的认知收益,因此 C++ 只保留长度分类后的双指针主解。