C++ standard solution


  • 3
    G
    /*
        dp[i][j] 代表从A[1...i]变换到B[1....j]需要的最少的步骤
        
        可以分为三种几种情况进行讨论:
            1、A[i]=B[j], 则从A[1...i]变换到B[1...j]的步数 dp[i][j] = dp[i-1][j-1]
            2 A[i] != B[j]:
            
                (1) 在A[i]后插入一个字符ch(ch=B[j]),耗费一步,那么问题转换为 A[1...i] --> B[1...j-1]的转换了(dp[i][j] = dp[i][j-1] + 1)
                    如  asdfe --> asdert  当前A[i] = e, B[j]=t,在A[i]后插入一个t(asdeft --> asdert),耗费一步,
                    则问题转换为 asdfe --> asder 变换的步骤了A[i] --> B[j-1]
                    
                (2) 将A[i]删除,耗费一步,则问题转换为A[i...i-1] -->B[1...j] 的转换了(dp[i][j] = dp[i-1][j] + 1)
                
                (3) 将A[i]替换为B[j],耗费一步, 则问题转换为 A[1...i-1] --> B[1...j-1]的转换了(dp[i][j] = dp[i-1][j-1] + 1)
                
                最后取三种转换的方式中步数最小的那种方案: dp[i+1][j+1] = min( min(dp[i+1][j]+1, dp[i][j+1]+1), dp[i][j]+1)
                         
    */
    
    
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m = word1.size(), n = word2.size();
            if(m==0 || n==0 )return max(m,n);
            int dp[m+1][n+1];
            for(int i=0; i<=m; i++)  dp[i][0] = i;
            for(int i=0; i<=n; i++)  dp[0][i] = i;
            for(int i=0; i<m; i++) {
                for(int j=0; j<n; j++) {
                    if(word1[i] == word2[j]) dp[i+1][j+1] = dp[i][j];
                    else dp[i+1][j+1] = min( min(dp[i+1][j]+1, dp[i][j+1]+1), dp[i][j]+1);
                }
            }
            return dp[m][n];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.