Sharing my 44ms C++ solution


  • 0
    T
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int n1 = word1.length();
            int n2 = word2.length();
            
            // application of dynamic programming
            vector<vector<int>> DP;
            DP.resize(n1+2);
            int i, j;
            for(i=0; i<=n1; i++)
                DP[i].resize(n2+2, 10000000);
            DP[0][0] = 0; 
            // DP[i][j] is minDistance(word1[0,...,i-1], word2[0,...,j-1])
            
            for(i=0; i<=n1; i++)
            {
                for(j=0; j<=n2; j++)
                {
                    if(i<n1)
                        DP[i+1][j] = min(DP[i+1][j], DP[i][j]+1);
                    // insert character for word2 or delete character for word1
                    if(j<n2)
                        DP[i][j+1] = min(DP[i][j+1], DP[i][j]+1);
                    // insert character for word1 or delete character for word2
                    if(i<n1 && j<n2)
                    {
                        if(word1[i] == word2[j])
                            DP[i+1][j+1] = min(DP[i+1][j+1], DP[i][j]);
                        else
                            DP[i+1][j+1] = min(DP[i+1][j+1], DP[i][j]+1); // replace a character
                    }
                }
            }
            return DP[n1][n2];
        }
    };

Log in to reply
 

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