首页 > 代码库 > Edit Distance
Edit Distance
https://oj.leetcode.com/problems/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
解题思路：
这时比较难的一道动态规划题目。难在两点。第一，需要考虑两个字符串的坐标，也就是说是一个二维dp。第二，状态转换方程的推导比较难。
开始，我很快想到LCS（longest common string）的方法，以为只要求出两个字符串的LCS长度， 那么操作步骤就是两个字符串的较长的长度减去LCS长度。于是，写出了下面的代码。
public class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); if(m == 0 && n == 0){ return 0; } if(m + n == 1){ return 1; } int[][] dp = new int[m][n]; if(word1.substring(0, 1).equals(word2.substring(0,1))){ dp[0][0] = 1; }else{ dp[0][0] = 0; } if(m > 1 && (word1.charAt(1) == word2.charAt(0) || word1.charAt(0) == word2.charAt(0))){ dp[1][0] = 1; } if(n > 1 && (word1.charAt(0) == word2.charAt(1) || word1.charAt(0) == word2.charAt(0))){ dp[0][1] = 1; } for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ if(word1.charAt(i) == word2.charAt(j)){ dp[i][j] = dp[i - 1][j - 1] + 1; }else{ dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return Math.max(m, n) - dp[m - 1][n - 1]; }}
这个代码惨败在如下的用例中：
| Input: | "ab", "bc" |
| Output: | 1 |
| Expected: | 2 |
可以看到，错位的需要两步。想到这里，我考虑LCS的方法一定是不行的，因为无法区分replace和delete then insert的情况。考虑再三，只能看答案。自己再想，也不难。
定义dp[i][j]为字符串A的前i个字符变成B字符串前j个字符所需要的步骤数量。这时考虑dp[i + 1][j + 1]。如果A[i + 1] == B[j + 1]，显然不需要任何步骤，A已经可以是B。那么dp[i + 1][j + 1]=dp[i][j]。如果不等呢？那一定是要将A[i + 1] 替换为B[j + 1]，所以步骤要+1。问题是，再哪个基础上加一？
考虑将A[i + 1]变成B[j]，那么再变成B[j + 1]，就需要再加上B[j + 1]即可，即dp[i + 1][j + 1]=dp[i+1][j] + 1。第二中方案，将A[i]变成B[j + 1]，那么就需要删掉A[i + 1]。于是，dp[i + 1][j + 1]=dp[i][j + 1] + 1。第三种方案，将A[i]变成B[j]，然后将A[i + 1]替换为B[j + 1]，于是dp[i + 1][j + 1]=dp[i+1][j + 1] + 1。下面引用的是我自己尝试的另一种解释方法。
考虑A从A[i]变到A[i + 1]。有三种可以做的方案。以A[i]为基础，将A[i]已经变成了B[j + 1]，花费的步骤数为dp[i][j + 1]，那么需要再删除A[i + 1]。于是dp[i + 1][j + 1]=dp[i][j + 1] + 1。第二种情况，以A[i + 1]为基础，先将其变成B[j]，花费dp[i + 1][j + 1]步，那么需要再加上B[j + 1]。于是dp[i + 1][j + 1]=dp[i+1][j] + 1。第三种方案，先将A[i]变成B[j]，再将A[i + 1]替换为B[j + 1]。于是dp[i + 1][j + 1]=dp[i+1][j + 1] + 1。
综上，dp[i][j]就是三种情况里最小的，于是=min( dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)。
初始化的时候需要注意，dp[0][i] = i，dp[i][0] = i。因为0个字符要变成i个，必然要add，反之就是delete。代码如下。
public class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); if(m == 0 && n == 0){ return 0; } int[][] dp = new int[m + 1][n + 1]; for(int i = 0; i <= m; i++){ dp[i][0] = i; } for(int i = 0; i <= n; i++){ dp[0][i] = i; } for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ if(word1.charAt(i - 1) == word2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1]; }else{ dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } } } return dp[m][n]; }}
这个题目的状态转换方程还是比较难的，看懂后，还需要仔细捉摸才能真正搞懂。这道题其实是NLP（自然语言处理）里的一个课题，本身也是一个叫做Wagner–Fischer的方法。可以参见下面两个网页。
http://en.wikipedia.org/wiki/Edit_distance
http://en.wikipedia.org/wiki/Edit_distance
Edit Distance