一、題目

??字符串有三種編輯操作:插入一個(gè)英文字符、刪除一個(gè)英文字符或者替換一個(gè)英文字符。 給定兩個(gè)字符串，編寫一個(gè)函數(shù)判定它們是否只需要一次(或者零次)編輯。

??點(diǎn)擊此處跳轉(zhuǎn)題目。

示例 1:

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

示例 2:

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

二、C# 題解

法一：從第一個(gè)不同位置處判斷后續(xù)相同子串

??由題可知，在不同位置處，左方和右方的子串應(yīng)相同。因此，先尋找到第一個(gè)不同的字符，判斷其后方子串是否一致：

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 {// 方法：從第一個(gè)不同位置處判斷后續(xù)相同子串public bool OneEditAway(string first, string second) {int i = 0, j = 0; // 雙指針，i 遍歷 first，j 遍歷 second（可以用一個(gè)指針代替，因?yàn)?i 時(shí)刻等于 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;// 判斷后續(xù)內(nèi)容是否相同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) {// 判斷界限內(nèi)每個(gè)字符是否相等while (i < first.Length && j < second.Length) {if (first[i] != second[j]) return false;i++; j++;}// 判斷是否都到達(dá)了字符串末尾，避免出現(xiàn)其中一個(gè)字符串仍有后續(xù)內(nèi)容的情況return i == first.Length && j == second.Length;}
}

• 時(shí)間復(fù)雜度：$O(max(m,n))$，其中 $m,n$ 分別為字符串 $first,second$ 的長度。
• 空間復(fù)雜度：$O(1)$。

法二：前后序遍歷判斷第一個(gè)不同字符的位置關(guān)系

??使用前序遍歷找出兩個(gè)字符串不同字符的第一個(gè)位置 firstDif1, firstDif2，再用后序遍歷找出兩個(gè)字符串不同字符的第一個(gè)位置 lastDif1, lastDif2。依據(jù)這四個(gè)位置的關(guān)系來判斷字符串的關(guān)系：

1. 相等：firstDif1 == first.Length && lastDif1 == -1
   至于 firstDif2 == second.Length && lastDif2 == -1 可以不判斷，因?yàn)楸囟ù嬖凇?br /> $$\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 {// 前后序遍歷判斷第一個(gè)不同字符的位置關(guān)系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;}// 前序?qū)ふ业谝粋€(gè)不同字符的位置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++;}}// 后序?qū)ふ业谝粋€(gè)不同字符的位置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--;}}
}

• 時(shí)間復(fù)雜度：$O(max(m,n))$，其中 $m,n$ 分別為字符串 $first,second$ 的長度。
• 空間復(fù)雜度：$O(1)$。

---

優(yōu)化

??看到了題解中有大佬使用手段確保 first 長度不大于 second，寫法很好，借鑒一下。由于此題插入和刪除具有對(duì)稱性，因此可以做出如下優(yōu)化：

法一

??可以不判斷刪除的情況，減少一次遍歷。

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 是否達(dá)到末端即可if (j == second.Length) return true;// 判斷后續(xù)內(nèi)容是否相同，少判斷一種情況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;}
}

法二

??法二沒有必要了，因?yàn)闇p少“刪除”的情況，只減少了一次 int 比較的判斷，而可能多帶來一次參數(shù)拷貝（first 和 second 互換傳入?yún)?shù)）。