Java DP Solution Beats 99.81 % on Runtime BottonUp(Space - O(N))
\n__Recursive Approach__(TLE) : In this Approach for Word1 we have 3 Operations which are Insert, Delete or Replace.\n\nIf the First character of both of the Wo
\n__Recursive Approach__(TLE) : In this Approach for Word1 we have 3 Operations which are Insert, Delete or Replace.\n\nIf the First character of both of the Words are same then we need not to perform any of the Operation but if the Character is not same then we need to check which of the Operation among the insert, delete or replace will give the minimum answer.\n\nSo to find the minimum answer we need to check all of the 3 Possible Operations and then we will check among them which is minimum and then simply return the answer.\n\n**In Case the Character of both of the Word is Matching**\nSimply Skip the similar character and hunt for the dissimilar One in the Word1.\n\n**In Case the Character we are Checking is not matching with the Character of Word1**\n1. __Insert__ : In this Case we will Insert in Word1 the same Character as that of the Word2 so that we can make the Word1 to match Word2.\n2. __Delete__ : In this Case we will Delete the Character from the Word1 as the character was not matching with the Word2.\n3. __Replace__ : We will replace the dissimilar Character of the Word1 with Word2.\n\nNote : After calculating the Minimum of all of the Possible 3 Operations then we need to Add 1 to the answer as We have not included the cost of current Operation. \nFor e.g.,\nword1 = "horse"\nword2 = "ros"\n\n```\n                          (horse, ros)\n// First Character of both the Words are Different then 3 Operations will be Performed\n\t\t\t      /             |            \\\n\t\t     (Insert)        (Delete)       (Replace)\n\t\t\t   |                |                |\n\t\t(rhorse, ros)       (orse,ros)       (rorse,ros) \n// It is to be noted that the first Character of Word1 will surely become same as that of the Word2. In order to get minimun answer we need to perfrom such Operations Otherwise we will not get the Optimized answer.\n               |                |                |  // We can directly write this stage in next Operations\n          (horse, os)      (orse, ros)        (orse, os) \n\t\t /     |     \\          .                  |  //Simply Skip the Character\n(horse, s) (orse, ros) (orse, s).               (rse, s)\n    .           .          .    .                   .\n    .           .          .                        .\n    .           .          .                        .\n\tSo on.\n```\n**Base Case** : Base Condition should be if any of the Word is consumed completely then we need to stop working as not we cannot check if the characters are same or not.\n\nIn the Base case, 3 Cases are Possible :\n1. **Both of the Word are Consumed** : Then ans is zero as the empty Strings are also equal.\n2. **Word1 is Consumed** : In this case Word2 is available and now our work is to convert the empty String into the Word1, So we need to perform Insertions Equal to length of the Word2. Hence we can return the Length of the Word2.\n3.  **Word2 is Consumed** : In this case Word1 is available and now our work is to convert the this String into the Empty, So we need to perform deletions Equal to length of the Word1. Hence we can return the Length of the Word1.\n\nSo we will return Math.max(Word1.length(), Word1.length());\n```\npublic static int helper(String s1, String s2){\n\t\tif(s1.length() == 0 || s2.length() == 0){ // If length any of the Length is Consumed completely\n\t\t\treturn Math.max(s1.length(), s2.length()); // Discussed Above\n\t\t}\n\n\t\tif(s1.charAt(0) == s2.charAt(0)){ // If the Character matches\n\t\t\treturn helper(s1.substring(1),s2.substring(1)); // Skip both of the Characters\n\t\t}else{\n\t\t\tint insert = helper(s1, s2.substring(1)); // In case of Insertion Consume the S2 character\n\t\t\tint delete = helper(s1.substring(1), s2); // In case of Deletion Consume the S1 character\n\t\t\tint replace = helper(s1.substring(1), s2.substring(1)); // In case of Replace Consume the characters from both of the Strings\n\t\t\t\n\t\t\t\n\t\t\treturn Math.min(insert, Math.min(delete, replace)) + 1; //Return the minimum Operations among the 3 Operations + 1.\n\t\t}\n\t}\n```\n\n**TopDown Approach** : This Approach is Similar as discussed Above but In this Approach we will create and Save the calculated answer in an Array called as Storage.\n```\npublic static int helperTD(String s1, String s2, int[][] strg){\n\t\tif(s1.length() == 0 || s2.length() == 0){\n\t\t\treturn Math.max(s1.length(), s2.length());\n\t\t}\n\t\tint n = s1.length();\n\t\tint m = s2.length();\n\t\tif(strg[n][m] != 0){  //If we have Already Calculated the Answer\n\t\t\treturn strg[n][m]; // return the Saved Answer\n\t\t}\n\t\t\n\t\tif(s1.charAt(0) == s2.charAt(0)){\n\t\t\tstrg[n][m] = helperTD(s1.substring(1),s2.substring(1), strg); // Saving Answer\n\t\t\treturn strg[n][m];\n\t\t}else{\n\t\t\tint insert = helperTD(s1, s2.substring(1), strg);\n\t\t\tint delete = helperTD(s1.substring(1), s2, strg);\n\t\t\tint replace = helperTD(s1.substring(1), s2.substring(1), strg);\n\t\t\tstrg[n][m] = Math.min(insert, Math.min(delete, replace)) + 1; // Storing the calculated answer\n\t\t\treturn strg[n][m]; // return the Calculated Answer\n\t\t}\n\t}\n```\n\n**BottomUp Approach** : \n```\npublic static int helperBU(String s1, String s2){\n\t\tint[][] strg = new int[s1.length() + 1][s2.length() + 1];\n\t\tfor(int i = s1.length();i >= 0;i--){\n\t\t\tfor(int j = s2.length();j >= 0;j--){\n\t\t\t\tif(i == s1.length()){\n\t\t\t\t\tstrg[i][j] = s2.length() - j;\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t\tif(j == s2.length()){\n\t\t\t\t\tstrg[i][j] = s1.length() - i;\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t\tif(s1.charAt(i) == s2.charAt(j)){\n\t\t\t\t\tstrg[i][j] = strg[i + 1][j + 1];\n\t\t\t\t}else{\n\t\t\t\t\tint insert = strg[i][j + 1];\n\t\t\t\t\tint delete = strg[i + 1][j];\n\t\t\t\t\tint replace = strg[i + 1][j + 1];\n\t\t\t\t\tstrg[i][j] = Math.min(insert, Math.min(delete, replace)) + 1;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn strg[0][0];\n\t}\n```\n\n**BottomUp Efficient(Beats 99.81 % on Runtime)**\n\n```\npublic static int helperBU_Eff(String s1, String s2){\n\t\tint[] strg = new int[s2.length() + 1];\n\t\tfor(int i = s1.length();i >= 0;i--){\n\t\t\tint save = 0;\n\t\t\tfor(int j = s2.length();j >= 0;j--){\n\t\t\t\tif(i == s1.length()){\n\t\t\t\t\tstrg[j] = s2.length() - j;\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t\tif(j == s2.length()){\n\t\t\t\t\tsave = strg[j];\n\t\t\t\t\tstrg[j] = s1.length() - i;\n\t\t\t\t\tcontinue;\n\t\t\t\t}\n\t\t\t\tif(s1.charAt(i) == s2.charAt(j)){\n\t\t\t\t\tint temp = save;\n\t\t\t\t\tsave = strg[j];\n\t\t\t\t\tstrg[j] = temp;\n\t\t\t\t}else{\n\t\t\t\t\tint insert = strg[j + 1];\n\t\t\t\t\tint delete = strg[j];\n\t\t\t\t\tint replace = save;\n\t\t\t\t\tsave = strg[j];\n\t\t\t\t\tstrg[j] = Math.min(insert, Math.min(delete, replace)) + 1;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn strg[0];\n\t}\n```
[]