Edit Distance · 數據結構與算法/leetcode/lintcode題解

# Edit Distance - tags: [[DP_Two_Sequence](# "一般有兩個數組或者兩個字符串，計算其匹配關系. 通常可用 `f[i][j]`表示第一個數組的前 i 位和第二個數組的前 j 位的關系。")] ### Source - leetcode: [Edit Distance | LeetCode OJ](https://leetcode.com/problems/edit-distance/) - lintcode: [(119) Edit Distance](http://www.lintcode.com/en/problem/edit-distance/) ~~~ Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example Given word1 = "mart" and word2 = "karma", return 3. ~~~ ### 題解1 - 雙序列動態規劃兩個字符串比較，求最值，直接看似乎并不能直接找出解決方案，這時往往需要使用動態規劃的思想尋找遞推關系。使用雙序列動態規劃的通用做法，不妨定義`f[i][j]`為字符串1的前`i`個字符和字符串2的前`j`個字符的編輯距離，那么接下來尋找其遞推關系。增刪操作互為逆操作，即增或者刪產生的步數都是一樣的。故初始化時容易知道`f[0][j] = j, f[i][0] = i`, 接下來探討`f[i][j]` 和`f[i - 1][j - 1]`的關系，和 LCS 問題類似，我們分兩種情況討論，即`word1[i] == word2[j]` 與否，第一種相等的情況有： 1. `i == j`, 且有`word1[i] == word2[j]`, 則由`f[i - 1][j - 1] -> f[i][j]` 不增加任何操作，有`f[i][j] = f[i - 1][j - 1]`. 1. `i != j`, 由于字符數不等，肯定需要增/刪一個字符，但是增刪 word1 還是 word2 是不知道的，故可取其中編輯距離的較小值，即`f[i][j] = 1 + min{f[i - 1][j], f[i][j - 1]}`. 第二種不等的情況有： 1. `i == j`, 有`f[i][j] = 1 + f[i - 1][j - 1]`. 1. `i != j`, 由于字符數不等，肯定需要增/刪一個字符，但是增刪 word1 還是 word2 是不知道的，故可取其中編輯距離的較小值，即`f[i][j] = 1 + min{f[i - 1][j], f[i][j - 1]}`. 最后返回`f[len(word1)][len(word2)]` ### Python ~~~ class Solution: # @param word1 & word2: Two string. # @return: The minimum number of steps. def minDistance(self, word1, word2): len1, len2 = 0, 0 if word1: len1 = len(word1) if word2: len2 = len(word2) if not word1 or not word2: return max(len1, len2) f = [[i + j for i in xrange(1 + len2)] for j in xrange(1 + len1)] for i in xrange(1, 1 + len1): for j in xrange(1, 1 + len2): if word1[i - 1] == word2[j - 1]: f[i][j] = min(f[i - 1][j - 1], 1 + f[i - 1][j], 1 + f[i][j - 1]) else: f[i][j] = 1 + min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) return f[len1][len2] ~~~ ### C++ ~~~ class Solution { public: /** * @param word1 & word2: Two string. * @return: The minimum number of steps. */ int fistance(string word1, string word2) { if (word1.empty() || word2.empty()) { return max(word1.size(), word2.size()); } int len1 = word1.size(); int len2 = word2.size(); vector<vector<int> > f = \ vector<vector<int> >(1 + len1, vector<int>(1 + len2, 0)); for (int i = 0; i <= len1; ++i) { f[i][0] = i; } for (int i = 0; i <= len2; ++i) { f[0][i] = i; } for (int i = 1; i <= len1; ++i) { for (int j = 1; j <= len2; ++j) { if (word1[i - 1] == word2[j - 1]) { f[i][j] = min(f[i - 1][j - 1], 1 + f[i - 1][j]); f[i][j] = min(f[i][j], 1 + f[i][j - 1]); } else { f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]); f[i][j] = 1 + min(f[i][j], f[i][j - 1]); } } } return f[len1][len2]; } }; ~~~ ### Java ~~~ public class Solution { public int minDistance(String word1, String word2) { int len1 = 0, len2 = 0; if (word1 != null && word2 != null) { len1 = word1.length(); len2 = word2.length(); } if (word1 == null || word2 == null) { return Math.max(len1, len2); } int[][] f = new int[1 + len1][1 + len2]; for (int i = 0; i <= len1; i++) { f[i][0] = i; } for (int i = 0; i <= len2; i++) { f[0][i] = i; } for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { f[i][j] = Math.min(f[i - 1][j - 1], 1 + f[i - 1][j]); f[i][j] = Math.min(f[i][j], 1 + f[i][j - 1]); } else { f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]); f[i][j] = 1 + Math.min(f[i][j], f[i][j - 1]); } } } return f[len1][len2]; } } ~~~ ### 源碼解析 1. 邊界處理 1. 初始化二維矩陣(Python 中初始化時 list 中 len2 在前，len1 在后) 1. i, j 從1開始計數，比較 word1 和 word2 時注意下標 1. 返回`f[len1][len2]` ### 復雜度分析兩重 for 循環，時間復雜度為 O(len1?len2)O(len1 \cdot len2)O(len1?len2). 使用二維矩陣，空間復雜度為 O(len1?len2)O(len1 \cdot len2)O(len1?len2).