[数据结构与算法]编辑距离【leetcode 72】

解答

动态规划

class Solution {
public:
    int minDistance(string word1, string word2) {

        // 获取字符串 word1 的长度
        int m = word1.size();
        // 获取字符串 word2 的长度
        int n = word2.size();

        if(m==0||n==0) return max(m,n);

        // 设置二维数组 dp 用来储存 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[0][0] 表示 word1 的前 0 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[i][j] 表示 word1 的前 i 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[m][n] 表示 word1 的前 m 个字符转换为 word2 的前 n 个字符最少操作数
        vector<vector<int>> dp(m+1,vector<int>(n+1));

        dp[0][0] = 0;

        // dp[i][0] 表示 word1 的前 i 个字符转换为 word2 的前 0 个字符最少操作数
        // dp[i][0] 相当于给二维数组 dp 的第一列进行赋值操作
        // 只需要每次执行删除操作，就可以把 word1 的字符删除到 0 个字符
        for (int i = 1; i < m+1; i++)
        {
            dp[i][0] = i;
        }
        
        // dp[0][j] 表示 word1 的前 0 个字符转换为 word2 的前 j 个字符最少操作数
        // dp[0][j] 相当于给二维数组 dp 的第一行进行赋值操作
        // 只需要每次执行插入操作，就可以把 word1 的字符转行为 j 个字符
        for (int j = 1; j < n+1; j++)
        {
            dp[0][j] = j;            
        }
        
        // 通过两个 for 循环，设置二维数组 dp 中的所有元素的值
        // i 从 word1 的第 1 个字符一直到 m 个字符
        for (int i = 1; i < m+1; i++)
        {
            // j 从 word2 的第 1 个字符一直到 n 个字符
            for (int j = 1; j < n+1; j++)
            {
                if(word1[i-1]==word2[j-1]) 
                {
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])+1);
                }
                else
                {
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }            
        }
        // dp[m][n] 表示 word1 的前 m 个字符转换为 word2 的前 n 个字符最少操作数
        return dp[m][n];
    }
};