Aditya Verma's approach | LCS pattern based code  | DP solution
Intuition\nThe basic intuition is derived from the Aditya Verma\'s DP series on Youtube. The basic code format can be referred from his tutorial on LCS(Longest 
# Intuition\nThe basic intuition is derived from the Aditya Verma\'s DP series on Youtube. The basic code format can be referred from his tutorial on LCS(Longest Common Subsequence). Link shared at the end.\n\n# Approach\nGiven in the problem that we are allowed 3 ways to convert(match) one string to other string namely insertion, deletion and replacing the characters in the string.\n\nConsider the very last character on both the Strings and if it happens to be a match, then do you think we need any kind of operation to match this character. Obviously No . Hence 0 operations needed to match this and we continue to match next characters on the both strings. i.e. lower both the pointers.\n```dp[i][j] = dp[i-1][j-1]; // if it is already matching then number of  operations required to match will be 0 and we continue for remaining strings```\n\nIf the first character doesn\'t matches then we will tryout all the possibilities to convert because that\'s all we as programmers can do. And post that include the 1 operation which gives us the minimum value.\n\n1) Suppose if we are inserting a character (at i) then that inserted character will obviously be a match from other word(otherwise why would you think to insert). Hence lower the i\'th pointer by one and calculate for remaining. So this counts as 1 operation.\n```dp[i][j] = 1 + dp[i-1][j]```\n\n2) Similarly If we choose to delete a character (at i) then after deleting the character lower the current word pointer by one, since it matched already after deletion (Do not lower other word pointer here since we are yet to match this character after deletion.) So this count as 1 operation and calculate for remaining.\n```dp[i][j] = 1 + dp[i-1][j]```\n\n3) Similarly If we choose to replace a character (at i) then lower both the pointers by one. Both pointers because you would only replace with the character for which you want to match otherwise why would you replace with a non-matching character. This counts as 1 operation and calculate for remaining.\n```dp[i][j] = 1 + dp[i-1][j-1]```\n\n4) Now you need to include the operation which gives minimum of steps (1, 2, 3) described above and Add 1 to it. Because we have completed 1 operation and going for the remaining conversion/matches. We can write in a single line as below.\n```dp[i][j] = 1+ Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]))```\n\n4) **BASE CASES MODIFICATION** :  Consider you have word1 as empty string. Then you would need to insert all the characters of the other word one by one. Means the number of operations are equal to the length of the other word.\n```if(i == 0) dp[i][j] = j```\n Similarly consider word2 as empty then you need to delete all the characters of the word1 one by one. Means the no of operations equal to the length of the current word word1.\n```if(j == 0) dp[i][j] = i```\n\n# Complexity\n- Time complexity:\n$$O(nm)$$ \n\n- Space complexity:\n$$O(nm)$$ \n\n# Code\n```\nclass Solution {\n    public int minDistance(String word1, String word2) {\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+1; i++){ // initialization\n            for(int j=0; j<m+1; j++){\n                if(i == 0)\n                    dp[i][j] = j;\n                if(j == 0)\n                    dp[i][j] = i;\n            }\n        }\n\n        for(int i=1; i<n+1; i++){ // logic\n            for(int j=1; j<m+1; j++){\n                if(word1.charAt(i-1) == word2.charAt(j-1))\n                    dp[i][j] = dp[i-1][j-1];\n                else\n                    dp[i][j] = 1+ Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));\n            }\n        }\n\n        return dp[n][m];\n    }\n}\n```\nNote: the code can be made more concise and space optimized by combining initialization and logic steps into one. But left as it is for better understanding.\n\nPlease UPVOTE if you understood the modifications needed on the existing Aditya Verma\'s code format. \n\nLink : Aditya verma\'s LCS format https://youtu.be/hR3s9rGlMTU\n
['Dynamic Programming', 'Recursion', 'Java']