recursion, dp
recursion, exponential\n\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        return recur(word1,word2,0,0);\n    }\n    \n    i
recursion, exponential\n```\nclass Solution {\n    public int minDistance(String word1, String word2) {\n        return recur(word1,word2,0,0);\n    }\n    \n    int recur(String word1, String word2, int index1, int index2) {\n        int n1 = word1.length(), n2 = word2.length();\n        if(n2==index2) return n1-index1;\n        if(n1==index1) return n2-index2;\n        \n        if(word1.charAt(index1)== word2.charAt(index2)) {\n            return recur(word1,word2,index1+1,index2+1);\n        } else {\n            int c1 = 1+recur(word1, word2,index1,index2+1); //insert\n            int c2 = 1+recur(word1, word2,index1+1,index2); //delete\n            int c3 = 1+recur(word1, word2,index1+1,index2+1); //replace\n            return Math.min(c1,Math.min(c2,c3));\n        }\n    }\n}\n```\ndp, time = O(mn), space = O(mn)\n```\nclass Solution {\n\n    public int minDistance(String word1, String word2) {\n        \n        int n1= word1.length(), n2=word2.length();\n        if(n1==0) return n2;\n        if(n2==0) return n1;\n        int[][] dp = new int[n1+1][n2+1];\n        //base\n         for(int i =0;i<n1+1;i++)  {    \n            dp[i][0] = i; //delete \n         }\n\n         for(int j =0;j<n2+1;j++)  {    \n            dp[0][j] = j; //add \n         }\n         \n        for(int i = 1;i<n1+1; i++) {\n            for(int j = 1;j<n2+1; j++) {\n            \n                if(word1.charAt(i-1) ==word2.charAt(j-1)) {\n                    dp[i][j] = dp[i-1][j-1];\n                } else {\n                    int c1 = dp[i-1][j]; //insert \n                    int c2 = dp[i][j-1]; //delete\n                    int c3 = dp[i-1][j-1]; //replace            \n                    dp[i][j] =1+ Math.min(Math.min(c1,c2),c3);\n                }\n            }\n        }\n        return dp[n1][n2];\n    }\n}\n\n```\n
[]