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[i][j]来保存word1的前i个字符转成word的前j个字符所需要的最小步数。这样i,j就用1开始，0作为初始化。

我们来考虑dp[i][j]的计算。将word1的第i个元素表示a,word2的第j个元素表示为b。如果a==b，那么不用操作，进行下个字符遍历，dp[i][j]=dp[i-1][j-1]。如果a!=b，这个时候有三个操作：好好领会。

1、将a变为b。dp[i][j]=dp[i-1][j-1]+1。

2、将b加到a后面，dp[i][j]=dp[i][j-1]+1.//说明前面i个字符可以转成word2的j-1个字符，这时候需要转成j个字符，就得在i个字符后加一个

3、删除a。dp[i][j]=dp[i-1][j]+1.//说明a是多出来的，word1的前i-1个字符就可以转成word2的前j个字符，这里多出来一个只要一步删除就行。

当a.b不相同时，就是取三个步骤的最小值。

dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1.

代码：

class Solution {

    public int minDistance(String word1, String word2) {

        int len1=word1.length();

        int len2=word2.length();

        //dp[i][j]表示word1的前i个字符转换成word2的前j个字符需要的最小步数。0个字符用于存放初始值

        int[][] dp=new int[len1+1][len2+1];

        for(int i=0;i<=len1;i++) dp[i][0]=i;//将Word1转成word2的前0个字符，就是删除word1的所有字符，也就是i步操作

        for(int j=0;j<=len2;j++) dp[0][j]=j;

        for(int i=1;i<=len1;i++)

            for(int j=1;j<=len2;j++){

                if(word1.charAt(i-1)==word2.charAt(j-1)){

                    dp[i][j]=dp[i-1][j-1];

                }else{

                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;

                }

            }

        return dp[len1][len2];

    }

}

巴特西

edit distance(编辑距离，两个字符串之间相似性的问题)

最新文章

热门文章