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

原问题链接：https://leetcode.com/problems/edit-distance/

 

问题分析

　　这是一个典型的动态规划方法应用的问题。这一类的问题相对来说都有一个递归最优解以及重复利用子问题解的特点。 我们先从问题的描述来找一下思路。

　　对于问题来说，对于一个字符串转换成另外一个字符串，它可以有这么几种变换，一种是增加一个字符，一种是删除一个字符以及替换一个字符。这样的一个操作相当于对源字符串做了一次转换。如果对于两个相同的字符串来说，它们则没有任何转换。在这种情况下它的转换次数为0。而问题的目的是求得转换成目标串所需要的最小变换。

　　对于源串word1来说，假设它的长度为m，如果要看它和目标穿word2(假设长度为n)的匹配程度，我们不仅需要看两个串最后面位置的字符，还要综合比较前面的所有情况。假设用函数P(i, j)表示对应于word1的i位置和word2的j位置是的转换数。

• 当word1[m] == word2[n]的时候，这个时候我们发现一种转换方式，就是我们只需要去看word1[m - 1]和word2[n - 1]的匹配情况。因为这个时候它们最后的两个字符相同。相当于这种变换的值其实和P(m - 1, n - 1)相等。但是这种方式就是最少或者说最优的转换了吗？只怕未必。
• 按照前面的描述，我们的的字符串变换有３种方式。那么在前面如果word[m]!= word[n]的时候呢？我们可以有一种变换就是替换一个字符。这个时候使得当前的字符相等，然后再把这个变换加到P(m - 1, n - 1)上。
• 我们也还有一种可能就是删除一个字符，使得它们最终匹配。这个时候我们的变换就是在P(m - 1, n)的基础上加１。
• 还有一种情况就是增加一个字符，这个时候的变换就是在P(m, n - 1)的基础上加1。

　　针对上述的讨论，我们就得到了一个递归的关系。对于这个递归的关系里，不管是P(m - 1, n) , P(m, n - 1)还是P(m - 1, n - 1)，它们又都满足上面的那个递归的属性。所以说它就是构成了一个动态规划解决的前提条件。

　　从具体实现的角度来说，我们需要定义一个[m + 1][n + 1]的矩阵。第0行0列表示对于两个串来说都没有字符参与转换，所以它的值是0。而对于matrix[0][i]和matrix[i][0]来说，它所有的的变换就是对应的i值。因为这个时候相当于一方是从一个空的字符串转换成目标串，所以对应的变化就是i。这样就构成了一个递推的基本范围值。剩下具体的实现里就是按照每行每列的方式去考察p(i - 1, j) + 1, p(i, j - 1) + 1, p(i - 1, j - 1)或者p(i - 1, j - 1) + 1的值。取它们中间最小的那个作为部分最优解。最终的最佳整体结果值保存在matrix[m][n]中。

　　详细的实现如下：

 

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] matrix = new int[m + 1][n + 1];
        for(int i = 0; i <= m; i++) matrix[i][0] = i;
        for(int i = 0; i <= n; i++) matrix[0][i] = i;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++) {
                int temp = matrix[i - 1][j - 1] + ((word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1);
                matrix[i][j] = Math.min(
                    Math.min(temp, matrix[i - 1][j] + 1),
                    matrix[i][j - 1] + 1
                );
            }
        return matrix[m][n];
    }
}