Evolve from brute force to dp
We only need to edit one word because insert a char to word1 is equivalent to delete a char in word2 and vise versa. Replace a char in word1 is equivalent to re
We only need to edit one word because insert a char to word1 is equivalent to delete a char in word2 and vise versa. Replace a char in word1 is equivalent to replace a char in word2.\n1. O(3^max(n1,n2)) We edit word 1 only and there are 3 operations\n* c++\n```\n    int minDistance(string word1, string word2) {\n        return minDistance(0,0,word1,word2);\n    }\n    int minDistance(int p1, int p2, string &word1, string &word2) {\n        if(p1==word1.size()) return word2.size()-p2; //dist between a string and an empty string\n        if(p2==word2.size()) return word1.size()-p1;\n        if(word1[p1]==word2[p2]) return minDistance(p1+1,p2+1,word1,word2);\n        int ins = minDistance(p1,p2+1,word1,word2);\n        int del = minDistance(p1+1,p2,word1,word2);\n        int rpl = minDistance(p1+1,p2+1,word1,word2);\n        return min(ins,min(del,rpl))+1;\n    }\n```\n* java\n```\n\tpublic int minDistance(String word1, String word2) {\n        return minDist(0,0,word1,word2);  \n    }\n    private int minDist(int p1, int p2, String word1, String word2) {\n        int s1=word1.length(),s2=word2.length();\n        if(p1==s1) return s2-p2; //We only edit word1, but since both insert and delete are allowed, word1 may not finish first\n        if(p2==s2) return s1-p1; //The two ternimation checks make sure both indexes are valid\n        if(word1.charAt(p1)==word2.charAt(p2)) \n            return minDist(p1+1,p2+1,word1,word2);\n        int ins = minDist(p1,p2+1,word1,word2);\n        int del = minDist(p1+1,p2,word1,word2);\n        int rep = minDist(p1+1,p2+1,word1,word2);\n        return Math.min(ins, Math.min(del, rep))+1;\n    }\n}\n```\n2. O(n1n2) memorization\n* c++\n```\n    int minDistance(string word1, string word2) {\n        vector<vector<int>> mem(word1.size(),vector<int>(word2.size(),-1));\n        return minDistance(0,0,word1,word2,mem);\n    }\n    int minDistance(int p1, int p2, string &word1, string &word2,vector<vector<int>>& mem) {\n        if(p1==word1.size()) return word2.size()-p2;\n        if(p2==word2.size()) return word1.size()-p1;\n        if(mem[p1][p2]>=0) return mem[p1][p2];\n        if(word1[p1]==word2[p2]) return mem[p1][p2]=minDistance(p1+1,p2+1,word1,word2,mem);\n        int ins = minDistance(p1,p2+1,word1,word2,mem);\n        int del = minDistance(p1+1,p2,word1,word2,mem);\n        int rpl = minDistance(p1+1,p2+1,word1,word2,mem);\n        return mem[p1][p2] = min(ins,min(del,rpl))+1;\n    }\n```\n* java\n```\n\tpublic int minDistance(String word1, String word2) {\n        Integer[][] mem=new Integer[word1.length()][word2.length()];\n        return minDist(0,0,word1,word2,mem);  \n    }\n    private int minDist(int p1, int p2, String word1, String word2, Integer[][] mem) {\n        int s1=word1.length(),s2=word2.length();\n        if(p1==s1) return s2-p2; //We only edit word1, but since both insert and delete are allowed, word1 may not finish first\n        if(p2==s2) return s1-p1; //The two ternimation checks make sure both indexes are valid\n        if(mem[p1][p2]!=null) return mem[p1][p2];\n        if(word1.charAt(p1)==word2.charAt(p2)) \n            return mem[p1][p2]=minDist(p1+1,p2+1,word1,word2,mem);\n        int ins = minDist(p1,p2+1,word1,word2,mem);\n        int del = minDist(p1+1,p2,word1,word2,mem);\n        int rep = minDist(p1+1,p2+1,word1,word2,mem);\n        return mem[p1][p2]=Math.min(ins, Math.min(del, rep))+1;\n    }\n```\n3. O(n1n2) dp\n* c++\n```\n    int minDistance(string word1, string word2) {\n        int n1 = word1.size(),n2=word2.size();\n        vector<vector<int>> dp(n1+1,vector<int>(n2+1));\n        for(int i=0;i<n1;i++) dp[i][n2] = n1-i;\n        for(int j=0;j<n2;j++) dp[n1][j] = n2-j;\n        for(int i=n1-1;i>=0;i--)\n            for(int j=n2-1;j>=0;j--) \n                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;\n        return dp[0][0];\n    }\n```\n* java\n```\n\tpublic int minDistance(String word1, String word2) {\n        int n1=word1.length(), n2=word2.length();\n        int[][] dp=new int[n1+1][n2+1];\n        for(int i=0;i<n1;i++) dp[i][n2]=n1-i;\n        for(int i=0;i<n2;i++) dp[n1][i]=n2-i;\n        for(int i=n1-1;i>=0;i--)\n            for(int j=n2-1;j>=0;j--) {\n                if(word1.charAt(i)==word2.charAt(j))\n                    dp[i][j]=dp[i+1][j+1];\n                else {\n                    dp[i][j]=Math.min(dp[i][j+1],Math.min(dp[i+1][j],dp[i+1][j+1]))+1;\n                }\n            }\n        return dp[0][0];  \n    }\n```\n4. linear space dp\n```\n    int minDistance(string word1, string word2) {\n        int s1=word1.size(),s2=word2.size();\n        vector<int> dp(s1+1);\n        iota(dp.rbegin(),dp.rend(),0);\n        for(int i=s2-1;i>=0;i--) {\n            int i1j1 = dp[s1];\n            dp[s1] = s2-i;\n            for(int j=s1-1;j>=0;j--) {\n                int temp=dp[j];\n                dp[j]=min(dp[j+1]+1,min(dp[j]+1,i1j1+(word2[i]!=word1[j])));\n                i1j1=temp;\n            }\n        }\n        return dp[0];\n    }\n```
['C', 'Java']