Step By Step Explanation From Brute force to Optimised DP !
\nIt took a lot of time and efforts to make this post please upvote if you like it and found helpful ! \n\nStep By Step Explanation :-\n\n For each poisition, c
\n***It took a lot of time and efforts to make this post please upvote if you like it and found helpful !*** \n\n**Step By Step Explanation :-**\n\n For each poisition, check three subproblem:\n      1. insert\n      2. delete\n      3. replace\n\nI was having trouble with this and figuring out the recurrences for the edit operations. i and j basically keep track of the current characters that are getting compared, each operation shifts them differently. **The important thing to note is that we are simulating the edit operations by moving i and j around**, not actually changing the input strings.\n\n**EXAMPLE**\nc1 = sample, c2 = example\ni = 0 (s), j = 0 (e)\n**Replace** is simplest for me to understand, we replace the cur char with the char we need from word2. We then increment i and j to look at the next char.\n*Replace -> match(c1,c2, i+1, j+1)*\nc1 = eample, c2 = example\ni = 1 (a), j = 1 (x)\n\n**Delete** removes the first character, shifting word 1 character to left. Since we do not actually delete the char, incrementing i simulates skipping this char.\n*Delete -> match(c1, c2, i+1, j)*\nc1 = sample, c2 = example\ni = 1 (a) , j = 0 (e)\n\n**Insert** is the opposite of delete, we insert the char we need, shifting word 1 to the right. Since we do not actually add a char, leave i alone. It\'s the similar as doing:\n\n  c1 = "e" + c1;\n  match(c1,c2,i+1,j+1) //Since we added "e", i+1 would point to "s"\n*Insert -> match(c1, c2, i, j+1)*\nc1 = esample, c2 = example\ni = 0 (s), j = 1 (x)\n\nHopefully I made sense, let me know if I can try to clarify more. I only recently was able to understand. Now lets jump to the Code part !\n\n***Method 1 : Recursion \nTime Complexity : O(3^(min(len1,len2))  \nSpace Complexity : O(n)***\n\n```\nclass Solution {\npublic:\n    int editDistance(int i , int j , string& s1 , string& s2)\n    {\n        if (i == word1.size()) return word2.size() - j;\n        if (j == word2.size()) return word1.size() - i;\n        if( s1[i] == s2[j] ) return editDistance(i+1 , j+1, s1, s2);\n        return 1 + min( editDistance(i , j+1, s1, s2), min( editDistance(i+1 , j, s1, s2),  editDistance(i+1 , j+1, s1, s2)));  // Didn\'t Got it , No issue again go through the explanation !\n    }\n   \n    int minDistance(string word1, string word2) {\n    return editDistance(0, 0, word1 , word2);\n    }\n};\n```\nOfcourse It will give TLE , so for it we will precompute sub - problem and will store it in bottom - up and top - down manner using Dynamic Programming!\n\n\n***Method 2 : Recursion + Memorisation ( Top - Down Approach )***\n Time Complexity   :  O(len1 x len2) \n Space Complexity : O(len1 x len2) \n\n```\nclass Solution {\npublic:\n    int editDistance(int i , int j , string& s1 , string& s2, vector<vector<int>>&dp)\n    {\n        if(i == size(s1) ) return size(s2) - j;\n        if(j == size(s2) ) return size(s1) - i;\n        if(dp[i][j] != -1) return dp[i][j];\n        if( s1[i] == s2[j] ) return dp[i][j] = editDistance(i+1 , j+1, s1, s2, dp);\n        return dp[i][j] = 1 + min( editDistance(i , j+1, s1, s2, dp), min( editDistance(i+1 , j, s1, s2, dp),  editDistance(i+1 , j+1, s1, s2, dp)));\n    }\n   \n    int minDistance(string word1, string word2) {\n    vector<vector<int>>dp(size(word1), vector<int>(size(word2), -1));\n    return editDistance(0, 0, word1 , word2, dp);\n    }\n};\n```\n\n\n***Method 3 : Tabulation ( Bottom - Up Approach)*** \n***Time Complexity   : O(len1 x len2)\nSpace Complexity : O(len1 x len2)***\n\n```\nclass Solution {\npublic:\n    int minDistance(string word1, string word2) {\n    int n = size(word1); int m = size(word2);\n    vector<vector<int>>dp(n+1, vector<int>(m+1,0));\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    for(int i = 0 ; i < n; i++)\n    {\n        for(int j = 0 ; j < m; j++)\n        {\n           if( word1[i] == word2[j] ) \n           dp[i+1][j+1] = dp[i][j];\n           else\n           dp[i + 1][j + 1] = min({dp[i][j + 1], dp[i + 1][j], dp[i][j]}) + 1;\n\t\t   //Since it is bottom up, we are considering in the ascending order of indexes.\n           //Insert means plus 1 to j, delete means plus 1 to i, replace means plus 1 to both i and j. \n           //above sequence is delete, insert and replace. \n        }\n    }\n    \n    return dp[n][m];\n    }\n};\n```\n\n***It took a lot of time and efforts to make this post please upvote if you like it and found helpful !***
['Recursion', 'Memoization', 'C']