6ms O(n) space - C++ solution!


  • 0
    B

    The solution uses only 2 array - prev and curr of size O(n) instead of nxn table for Edit Distance.

    class Solution {
    public:
        int minDistance(string word1, string word2) {
            if(word1.size() == 0)
                return word2.size();
            if (word2.size() == 0)
                return word1.size();
            vector<int> curr(word2.size()+1, 0);
            vector<int> prev(word2.size()+1, 0);
            for(int i=0;i<prev.size();)
                prev[i]=i++;
            
            for(int j=0;j<word1.size();j++){
                curr[0] = j+1;
                for(int i = 0; i<word2.size();i++){
                            curr[i+1] = min(1+curr[i], min(1+prev[i+1], (word2[i]==word1[j]?0:1) + prev[i]));
                }        
                prev = curr;
            }
                
            return curr[curr.size()-1];
        }
    };```

Log in to reply
 

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