Share my C++ solution,easy to understand


  • 0
    V

    https://en.wikipedia.org/wiki/Edit_distance

    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int len1 = word1.size();
            int len2 = word2.size();
            
            if (len1 == 0)
                return len2;
            if (len2 == 0)
                return len1;
            
            int dp[len1+1][len2+1];
            
            for (int i = 0; i <= len2; i++)
                dp[0][i] = i;
            
            for (int i = 0; i <= len1; i++)
                dp[i][0] = i;
                
            for (int row = 1; row <= len1; row++)
            {
                for (int col = 1; col <= len2; col++)
                {
                    dp[row][col] = min(dp[row][col - 1], dp[row - 1][col]) + 1;
                    
                    if (word1[row-1] == word2[col-1])
                        dp[row][col] = min(dp[row][col], dp[row-1][col-1]);
                    else
                        dp[row][col] = min(dp[row][col], dp[row-1][col-1] + 1);
                }
            }
            
            return dp[len1][len2];
        }
    };
    

  • 0
    V

    Optimization in Space Complexity:

    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int len1 = word1.size();
            int len2 = word2.size();
            
            if (len1 == 0)
                return len2;
            if (len2 == 0)
                return len1;
            
            len1++;
            len2++;
            int dp_pre[len2];
            int dp_cur[len2];
            
            for (int i = 0; i < len2; i++)
                dp_pre[i] = i;
                
            for (int row = 1; row < len1; row++)
            {
                dp_cur[0] = row;
                
                for (int col = 1; col < len2; col++)
                {
                    dp_cur[col] = min(dp_cur[col-1], dp_pre[col]) + 1;
                    dp_cur[col] = min(dp_cur[col], dp_pre[col-1] + (word1[row-1] == word2[col-1] ? 0 : 1));
                }
                
                for (int k = 0; k < len2; k++)
                    dp_pre[k] = dp_cur[k];
            }
            
            return dp_cur[len2-1];
        }
    };

Log in to reply
 

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