LeetCode 面试题 01.05. 一次编辑

一、题目

  字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

  点击此处跳转题目。

示例 1:

输入:
first = “pale”
second = “ple”
输出: True

示例 2:

输入:
first = “pales”
second = “pal”
输出: False

二、C# 题解

法一：从第一个不同位置处判断后续相同子串

  由题可知，在不同位置处，左方和右方的子串应相同。因此，先寻找到第一个不同的字符，判断其后方子串是否一致：

1. 替换：IsSame(first, i + 1, second, j + 1)
   $$\begin{array}{lcccccc}& h& o& r& s& e& (first)\\ i:& & & & \uparrow & & \\ & & & & & & \\ & h& o& r& t& e& (second)\\ j:& & & & \uparrow & & \end{array}$$

2. 插入：IsSame(first, i, second, j + 1)
   $$\begin{array}{lccccccc}& h& o& r& s& e& & (first)\\ i:& & & & \uparrow & & & \\ & & & & & & & \\ & h& o& r& t& s& e& (second)\\ j:& & & & \uparrow & & & \end{array}$$

3. 删除：IsSame(first, i + 1, second, j)
   $$\begin{array}{lcccccc}& h& o& r& s& e& (first)\\ i:& & & & \uparrow & & \\ & & & & & & \\ & h& o& r& e& & (second)\\ j:& & & & \uparrow & & \end{array}$$

public class Solution {// 方法：从第一个不同位置处判断后续相同子串public bool OneEditAway(string first, string second) {int i = 0, j = 0; // 双指针，i 遍历 first，j 遍历 second（可以用一个指针代替，因为 i 时刻等于 j）// 前序遍历寻找第一处不同while (i < first.Length && j < second.Length) { if (first[i] != second[j]) break;i++; j++;}// 判断字符串相等if (i == first.Length && j == second.Length) return true;// 判断后续内容是否相同return IsSame(first, i + 1, second, j) || IsSame(first, i, second, j + 1) || IsSame(first, i + 1, second, j + 1);}// 判断从位置 i 开始的 first 字符串和从位置 j 开始的 second 字符串是否相等public bool IsSame(string first, int i, string second, int j) {// 判断界限内每个字符是否相等while (i < first.Length && j < second.Length) {if (first[i] != second[j]) return false;i++; j++;}// 判断是否都到达了字符串末尾，避免出现其中一个字符串仍有后续内容的情况return i == first.Length && j == second.Length;}
}

• 时间复杂度：$O(max(m,n))$，其中 $m,n$ 分别为字符串 $first,second$ 的长度。
• 空间复杂度：$O(1)$。

法二：前后序遍历判断第一个不同字符的位置关系

  使用前序遍历找出两个字符串不同字符的第一个位置 firstDif1, firstDif2，再用后序遍历找出两个字符串不同字符的第一个位置 lastDif1, lastDif2。依据这四个位置的关系来判断字符串的关系：

1. 相等：firstDif1 == first.Length && lastDif1 == -1
   至于 firstDif2 == second.Length && lastDif2 == -1 可以不判断，因为必定存在。
   $$\begin{array}{lcccccccc}& & h& o& r& s& e& & \\ lastDif1:& \uparrow & & & & & & \uparrow & :firstDif1\\ & & & & & & & & \\ & & h& o& r& s& e& & \\ lastDif2:& \uparrow & & & & & & \uparrow & :firstDif2\end{array}$$

2. 替换：firstDif1 == lastDif1 && firstDif2 == lastDif2
   $$\begin{array}{lcccccccc}& & h& o& r& s& e& & \\ firstDif1:& & & & & \uparrow \uparrow & & & :lastDif1\\ & & & & & & & & \\ & & h& o& r& t& e& & \\ firstDif2:& & & & & \uparrow \uparrow & & & :lastDif2\end{array}$$

3. 插入：firstDif1 - 1 == lastDif1 && firstDif2 == lastDif2
   $$\begin{array}{lccccccccc}& & h& o& r& s& e& & & \\ lastDif1:& & & & \uparrow & \uparrow & & & :firstDif1& \\ & & & & & & & & & \\ & & h& o& r& t& s& e& & \\ firstDif2:& & & & & \uparrow \uparrow & & & :lastDif2& \end{array}$$

4. 删除：firstDif1 == lastDif1 && firstDif2 - 1 == lastDif2
   $$\begin{array}{lcccccccc}& & h& o& r& s& e& & \\ firstDif1:& & & & & \uparrow \uparrow & & & :lastDif1\\ & & & & & & & & \\ & & h& o& r& e& & & \\ lastDif2:& & & & \uparrow & \uparrow & & & :firstDif2\end{array}$$

public class Solution {// 前后序遍历判断第一个不同字符的位置关系public bool OneEditAway(string first, string second) {int firstDif1, firstDif2, lastDif1, lastDif2;FirstDiffer(first, out firstDif1, second, out firstDif2);LastDiffer(first, out lastDif1, second, out lastDif2);// 相等if (firstDif1 == first.Length && lastDif1 == -1) return true;// 替换if (firstDif1 == lastDif1 && firstDif2 == lastDif2) return true;// 插入if (firstDif1 - 1 == lastDif1 && firstDif2 == lastDif2) return true;// 删除if (firstDif1 == lastDif1 && firstDif2 - 1 == lastDif2) return true;return false;}// 前序寻找第一个不同字符的位置public void FirstDiffer(string first, out int firstDif1, string second, out int firstDif2) {firstDif1 = firstDif2 = 0;while (firstDif1 < first.Length && firstDif2 < second.Length) {if (first[firstDif1] != second[firstDif2]) return;firstDif1++; firstDif2++;}}// 后序寻找第一个不同字符的位置public void LastDiffer(string first, out int lastDif1, string second, out int lastDif2) {lastDif1 = first.Length - 1;lastDif2 = second.Length - 1;while (lastDif1 >= 0 && lastDif2 >= 0) {if (first[lastDif1] != second[lastDif2]) return;lastDif1--; lastDif2--;}}
}

• 时间复杂度：$O(max(m,n))$，其中 $m,n$ 分别为字符串 $first,second$ 的长度。
• 空间复杂度：$O(1)$。

---

优化

  看到了题解中有大佬使用手段确保 first 长度不大于 second，写法很好，借鉴一下。由于此题插入和删除具有对称性，因此可以做出如下优化：

法一

  可以不判断删除的情况，减少一次遍历。

public class Solution {public bool OneEditAway(string first, string second) {if (first.Length > second.Length) // 确保 first 长度不大于 secondreturn OneEditAway(second, first);int i = 0, j = 0; while (i < first.Length && j < second.Length) { if (first[i] != second[j]) break;i++; j++;}// 判断字符串相等，只用判断 second 是否达到末端即可if (j == second.Length) return true;// 判断后续内容是否相同，少判断一种情况return IsSame(first, i, second, j + 1) || IsSame(first, i + 1, second, j + 1);}public bool IsSame(string first, int i, string second, int j) {while (i < first.Length && j < second.Length) {if (first[i] != second[j]) return false;i++; j++;}return i == first.Length && j == second.Length;}
}

法二

  法二没有必要了，因为减少“删除”的情况，只减少了一次 int 比较的判断，而可能多带来一次参数拷贝（first 和 second 互换传入参数）。