## Tuesday, November 25, 2014

### [LeetCode] 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:
a) Insert a character
b) Delete a character
c) Replace a character

1. 状态：
DP[i+1][j+1]：word1[0:i] -> word2[0:j]的edit distance。

2. 通项公式：

a) 插入一个字符：word1[0:i] -> word2[0:j-1]，然后在word1[0:i]后插入word2[j]
DP[i+1][j+1] = DP[i+1][j]+1

b) 删除一个字符：word1[0:i-1] -> word2[0:j]，然后删除word1[i]
DP[i+1][j+1] = DP[i][j+1]+1

c) 替换一个字符：word1[0:i-1] -> word2[0:j-1]
word1[i] != word2[j]时，word1[i] -> word2[j]：DP[i+1][j+1] = DP[i][j] + 1
word1[i] == word2[j]时：DP[i+1][j+1] = DP[i][j]

DP[i+1][j+1] = min(DP[i][j] + k, DP[i+1][j]+1, DP[i][j+1]+1)
word1[i]==word2[j] -> k = 0, 否则k = 1

3. 计算方向：
replace (i, j)      delete (i, j+1)
insert (i+1, j)    (i+1, j+1)

4. 起始、边界值
DP[0][i] = i： word1为空，要转化到word2[0:i-1]，需要添加i个字符。
DP[i][0] = i： word2为空，要从word1转化到空字符串，需要删除i个字符。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20``` ```class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector> dp(m+1, vector(n+1, 0)); for(int j=1; j<=n; j++) dp[0][j] = j; for(int i=1; i<=m; i++) { dp[i][0] = i; for(int j=1; j<=n; j++) { dp[i][j] = dp[i-1][j-1]; if(word1[i-1]!=word2[j-1]) dp[i][j]++; dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i][j]); } } return dp[m][n]; } }; ```

#### 1 comment:

1. 行了，哥们儿，你的解释比大多算法教科书上的简洁明了的太多太多了！