题解 | #牛群编号变更#

知识点

动态规划，一维线性

思路

可以发现对word1操作和对word2操作是等效的，对两个word来说，一个word的增加/删除可以转换为另一个word的删除/增加，无论怎么样操作不会改变总的步数

为了方便理解，我们假设（字符串下标从1开始），实际做题的时候将字符串右移一位即可 假设len1为word1的长度，len2为word2的长度

由于只有两种操作，所以每个状态只有可能通过两种方式转移。假设dp[i][j]代表将word1的[1.....i]转换为word2[1.....j]位的最小操作步数，那么有两种情况

①word1[i]与word2[j]不同，那么可以通过在word1末尾增加一位或在word1末尾增加一位：

对增加操作，加完后，word1[1....i]与Word2[1....j]匹配，那么加之前，word1[1...i-1]应当与word2[1...j]匹配

答案：dp[i-1][j]

对删除操作，删完后，word1[1....i]与Word2[1....j]匹配，那么加之前，word1[1...i]应当与word2[1...j-1]匹配

答案：dp[i][j-1]

②word1[i]==word2[j]

这种情况，不用操作，从dp[i-1][j-1]直接转移过来

答案：dp[i-1][j-1]

每次操作判断情况，并对答案取最小值，dp[len1][len2]即为所求

初始化：

由于所求属性是最小值，所以需要将dp数组初始化成一个大值：0x3f3f3f3f

对第0行，即dp[0][i]，代表word1的第0位转移到word2的[1~i]位，那么Word2有多少位就要转移多少次

对第0列，同理可得

代码（c++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param word1 string字符串 
     * @param word2 string字符串 
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        // write code here
       int dp[10005][10005];
       int len1=word1.length();
       int len2=word2.length();
       for(int i=1;i<=len1;i++)
       {
        for(int j=1;j<=len2;j++)
        {
             dp[i][j]=0x3f3f3f3f;
        }
       }
       for(int i=0;i<=len1;i++)//初始化第0行
       {
        dp[0][i]=i;
       }
       for(int i=0;i<=len2;i++)//初始化第0列
       {
        dp[i][0]=i;
       }

       for(int i=1;i<=len1;i++)
       {
        for(int j=1;j<=len2;j++)
        {   //判断条件减了一位，因为字符串下标从0开始，左移一位即可
           if(word1[i-1]!=word2[j-1])dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1; 
           else dp[i][j]=min(dp[i][j],dp[i-1][j-1]);       
        }
       }
      /* for(int i=0;i<=len1;i++)
       {
        for(int j=0;j<=len2;j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
       }*/
       return dp[len1][len2];
    }
};