16 ms (fastest so far) C++ DP O(mn) Time, O(n) Space.


  • 0
    F
    class Solution {
    public:
        int minDistance(const string &word1, const string& word2) {
            int * dp = new int [word2.size() + 1];
            int pre; // dp[i-1][j-1]
            for (int i = 0; i <= word1.size(); ++i)
            {
    
                for (int j = 0; j <= word2.size(); ++j)
                {
                    if (i == 0)
                    {
                        dp[j] = j;
                    }else if (j == 0)
                    {
                        pre = i - 1;
                        dp[j] = i;
                    }else if (word1[i - 1] == word2[j - 1])
                    {
                        swap(dp[j], pre);
                    }else{
                        int tmp = dp[j];
                        dp[j] = min(dp[j], min(dp[j - 1], pre)) + 1;
                        pre = tmp;
                    }
    
                }
            }
            return dp[word2.size()];
        }
    };

Log in to reply
 

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