583. 两个字符串的删除操作 72. 编辑距离

583. 两个字符串的删除操作

        dp[i][j]:以i-1结尾的word1和j-1结尾的word2 变成相同字符串最少的步骤为dp[i][j]

        初始化dp[i][0],dp[0][j]为空字符串和第一个字符匹配的最少步骤，即i/j，删除对应的字符个数。dp[i][0]=i,dp[0][j]=j;

        遍历两个字符串。

        若word1[i-1]==word2[j-1],则不需要对当前字符进行删除操作，操作步骤和dp[i-1][j-1]相同

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

        否则不相同，则有三种操作：

        ①删word1[i-1]，删除一次： dp[i][j]=dp[i-1][j]+1;

        ①删word1[j-1]，删除一次： dp[i][j]=dp[i][j-1]+1;

        ①删word1[i-1]和word2[j-1]，删除两次： dp[i][j]=dp[i-1][j-1]+2;

        取三者的最小值得到当前的最小步骤。        

                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][j-1]+1,dp[i-1][j-1]+2));}

        最后返回dp[len1][len2]即为使两个字符串相同所需删除的最小步骤

72. 编辑距离

        dp[i][j]:[0,i-1]长度的word1和[0,j-1]长度的word2相同所需要的最少步骤为dp[i][j]

        初始化dp[i][0],dp[0][j]为空字符串和第一个字符匹配的最少步骤，即i/j，删除对应的字符个数。

         遍历两个字符串。

        若word1[i-1]==word2[j-1],则不需要对当前字符进行删除操作，操作步骤和dp[i-1][j-1]相同

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

        否则不相同，则有三种操作：

        ①删除word1[i-1]，进行一次删除操作： dp[i][j]=dp[i-1][j]+1；

        ②删除word1[j-1]，进行一次删除操作： dp[i][j]=dp[i][j-1]+1；

        ③替换word1[i-1]为word2[j-1]/替换word2[j-1]为word1[i-1]: dp[i][j]=dp[i-1][j-1]+1；

注意：添加操作其实相当于删除操作。给word1添加一个元素和给word2删除一个元素所需步骤相同。

        最后取三者最小值。

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

        最后返回dp[len1][len2]即为最小步骤。