LCS pattern All-in-one Intuitive Approach Beats space and time
Code\njava []\n// Longest Common Subsequence\n// Approach - 1 Memorization\nclass Solution {\n    public int minDistance(String word1, String word2) {\n\n      
# Code\n```java []\n// Longest Common Subsequence\n// Approach - 1 Memorization\nclass Solution {\n    public int minDistance(String word1, String word2) {\n\n        int n = word1.length();\n        int m= word2.length();\n\n        int [][] dp = new int [n][m];\n        for(int [] i: dp) Arrays.fill(i,-1);\n\n        return solve(n-1,m-1,word1,word2,dp);                \n    }\n    int solve (int n, int m, String word1, String word2, int [][]dp){\n\n        if(n<0) return m+1;\n        if(m<0) return n+1;\n        \n        if(dp[n][m]!=-1) return dp[n][m];\n\n        if(word1.charAt(n)==word2.charAt(m)){\n            return dp[n][m] = solve(n-1,m-1,word1,word2,dp);// if word1 and word2 are same no operation is required to convert\n        }\n        int insert = solve(n,m-1,word1,word2,dp);\n        int delete = solve(n-1,m,word1,word2,dp);\n        int replace = solve(n-1,m-1,word1,word2,dp);\n\n        return dp[n][m] =1+ Math.min(insert,Math.min(delete,replace)); // if words are different "1" operation is required and how many more is recursively calculated\n    }\n}\n```\n```java []\n// Longest Common Subsequence\n// Approach - 1 Memorization\nclass Solution {\n    public int minDistance(String word1, String word2) {\n\n        int n = word1.length();\n        int m= word2.length();\n\n        int [][] dp = new int [n][m];\n        for(int [] i: dp) Arrays.fill(i,-1);\n\n        return solve(n-1,m-1,word1,word2,dp);                \n    }\n    int solve (int n, int m, String word1, String word2, int [][]dp){\n\n        if(n<0) return m+1;\n        if(m<0) return n+1;\n        \n        if(dp[n][m]!=-1) return dp[n][m];\n\n        if(word1.charAt(n)==word2.charAt(m)){\n            return dp[n][m] = solve(n-1,m-1,word1,word2,dp);// if word1 and word2 are same no operation is required to convert\n        }\n        // else words are different "1" operation is required and how many more is recursively calculated\n        int insert = 1+ solve(n,m-1,word1,word2,dp);\n        int delete = 1+ solve(n-1,m,word1,word2,dp);\n        int replace = 1+ solve(n-1,m-1,word1,word2,dp);\n\n        return dp[n][m] =Math.min(insert,Math.min(delete,replace)); \n    }\n}\n```\n```java []\n// Longest Common Subsequence\n// Approach - 2 Tabulation\nclass Solution {\n    public int minDistance(String word1, String word2) {\n\n        int n = word1.length();\n        int m= word2.length();\n\n        int [][] dp = new int [n+1][m+1];\n        \n        for(int i=0;i<=n;i++) dp[i][0]=i;\n        for(int j=0;j<=m;j++) dp[0][j]=j;\n\n        \n        for(int i=1;i<=n;i++){\n            for(int j=1;j<=m;j++){\n\n                if(word1.charAt(i-1)==word2.charAt(j-1)){\n\n                    dp[i][j]= dp[i-1][j-1]; // if word1 and word2 are same no operation is required to convert\n\n                }\n                else{ // if words are different "1" operation is required and how many more is recursively calculated\n\n                    int insert = 1+ dp[i][j-1];\n                    int delete = 1+ dp[i-1][j];\n                    int replace = 1+ dp[i-1][j-1];\n                    dp[i][j] = Math.min(insert,Math.min(delete,replace));\n                }\n            }\n        }\n        return dp[n][m];\n    }\n}\n```\n```java []\n// Longest Common Subsequence\n// Approach - 3 Space Optimized NOTE: in prev and cur\nclass Solution {\n    public int minDistance(String word1, String word2) {\n\n        int n = word1.length();\n        int m= word2.length();\n\n        int []prev = new int [m+1];\n        int []cur = new int [m+1];\n        \n        for(int j=0;j<=m;j++) prev[j]=j;\n\n        \n        for(int i=1;i<=n;i++){\n            \n            cur[0]=i;\n            for(int j=1;j<=m;j++){\n\n                if(word1.charAt(i-1)==word2.charAt(j-1)){\n\n                    cur[j]= prev[j-1]; // if word1 and word2 are same no operation is required to convert\n\n                }\n                else{ // if words are different "1" operation is required and how many more is recursively calculated\n\n                    int insert = 1+ cur[j-1];\n                    int delete = 1+ prev[j];\n                    int replace = 1+ prev[j-1];\n                    cur[j] = Math.min(insert,Math.min(delete,replace));\n                }\n            }\n            prev = (int [])(cur.clone());\n        }\n        return prev[m];\n    }\n}\n```\n
['String', 'Dynamic Programming', 'Java']