经典算法题型之编辑距离（二）

解题思路

简要概括题意，使用最少的操作使得「word1」与「word2」相同。很明显所要进行的操作是从左至右线性增长的，不难联想到最长公共子序列（LCS），因此我们令 f[i][j] 表示最少的操作使得 「word1」的前 i 个字符与「word2」的前 j 个字符相同。

C++ 代码实现

class Solution { public: int minDistance(string word1, string word2) { int n = word1.length(), m = word2.length(); vector<vector<int> > f(n+1, vector<int>(m+1, 0)); for(int i = 1; i <= n; i++) f[i][0] = i; for(int j = 1; j <= m; j++) f[0][j] = j; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(word1[i-1] == word2[j-1]) f[i][j] = f[i-1][j-1]; else f[i][j] = min(f[i-1][j-1]+1, min(f[i][j-1]+1, f[i-1][j]+1)); } } return f[n][m]; } };