Evolve from brute force to dp


  • 1
    1. O(3^max(n1,n2)) We edit word 1 only and there are 3 operations
        int minDistance(string word1, string word2) {
            return minDistance(0,0,word1,word2);
        }
        int minDistance(int p1, int p2, string &word1, string &word2) {
            if(p1==word1.size()) return word2.size()-p2; //dist between a string and a empty string
            if(p2==word2.size()) return word1.size()-p1;
            if(word1[p1]==word2[p2]) return minDistance(p1+1,p2+1,word1,word2);
            int ins = minDistance(p1,p2+1,word1,word2);
            int del = minDistance(p1+1,p2,word1,word2);
            int rpl = minDistance(p1+1,p2+1,word1,word2);
            return min(ins,min(del,rpl))+1;
        }
    

    2 O(n1n2) memorization

        int minDistance(string word1, string word2) {
            vector<vector<int>> mem(word1.size(),vector<int>(word2.size(),-1));
            return minDistance(0,0,word1,word2,mem);
        }
        int minDistance(int p1, int p2, string &word1, string &word2,vector<vector<int>>& mem) {
            if(p1==word1.size()) return word2.size()-p2;
            if(p2==word2.size()) return word1.size()-p1;
            if(mem[p1][p2]>=0) return mem[p1][p2];
            if(word1[p1]==word2[p2]) return mem[p1][p2]=minDistance(p1+1,p2+1,word1,word2,mem);
            int ins = minDistance(p1,p2+1,word1,word2,mem);
            int del = minDistance(p1+1,p2,word1,word2,mem);
            int rpl = minDistance(p1+1,p2+1,word1,word2,mem);
            return mem[p1][p2] = min(ins,min(del,rpl))+1;
        }
    

    3 O(n1n2) dp

        int minDistance(string word1, string word2) {
            int n1 = word1.size(),n2=word2.size();
            vector<vector<int>> dp(n1+1,vector<int>(n2+1));
            for(int i=0;i<n1;i++) dp[i][n2] = n1-i;
            for(int j=0;j<n2;j++) dp[n1][j] = n2-j;
            for(int i=n1-1;i>=0;i--)
                for(int j=n2-1;j>=0;j--) 
                    dp[i][j] = word1[i]==word2[j]? dp[i+1][j+1] : min(min(dp[i][j+1],dp[i+1][j]),dp[i+1][j+1])+1;
            return dp[0][0];
        }
    

    4 linear space dp

        int minDistance(string word1, string word2) {
            int s1=word1.size(),s2=word2.size();
            vector<int> dp(s1+1);
            iota(dp.rbegin(),dp.rend(),0);
            for(int i=s2-1;i>=0;i--) {
                int i1j1 = dp[s1];
                dp[s1] = s2-i;
                for(int j=s1-1;j>=0;j--) {
                    int temp=dp[j];
                    dp[j]=min(dp[j+1]+1,min(dp[j]+1,i1j1+(word2[i]!=word1[j])));
                    i1j1=temp;
                }
            }
            return dp[0];
        }
    

Log in to reply
 

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