C++ || Most Detailed || From Recursive to Space optmisation
Approach:\n\n--> Here we can follow string matching method where we will match every character using 2 variables i and j where i will traverse s1 and j will tra
## Approach:\n\n--> Here we can follow string matching method where we will match every character using 2 variables `i and j where i will traverse s1 and j will traverse s2` and then we will have 2 conditions:\n\n1. If they are matching:\n\t- then we will simply decrease both i and j \n\t- we are not applying any step here\n2. If they are not matching:\n\t- Then we have 3 possibilities here:\n\t\t- Insert s[j] character at that place\n\t\t- Delete this character and decrease i\n\t\t- Replace ith character with s[j]\n\t\t- we are applying any one of the step here so we will add 1 to total steps.\n\t\t\n--> Let\'s see all these conditions in bit detail:\n\n### If they are not matching:\n\n**1. If we insert s[j] character at that place:**\n\nTake a look at this example:\n\n![image](https://assets.leetcode.com/users/images/92c6e07c-3694-4fa5-8efc-5bbb83e3243c_1663240869.4235468.png)\n\nHere we will just decrease `j` because we have added jth character so they are matched.\n```cpp\n1 + solve(i,j-1);\n```\n\n**2. If we delete the ith character:**\n\nThen we will simply decrease `i`.\n```cpp\n1 + solve(i-1,j);\n```\n\n**3. If we replace the ith character:**\n\nHere we will ofcourse replace the ith character with s[j] and then they both will match and we will decrease both `i and j`.\n```cpp\n1 + solve(i-1,j-1);\n```\n\nAt last take the `minimum` of these 3 steps:\n\n### If they are matching:\n\njust decrease both i and j but don\'t add 1 in steps because we haven\'t performed any step here.\n\n```cpp\nsolve(i-1,j-1);\n```\n\n## Base case:\n\nHere we will have 2 conditions:\n\n1. If we have traversed all s1 string means i is negative and j is still have some value.\n\t- For example we have to make `ros` from `horse` and we have traversed whole horse string and j is at character `o` then we will have to make `ro` from empty string, so here we will perform `2 insert operations`.\n\t- so if i becomes negative then we will return `j+1`.\n2. If we have traversed all s2 string means j is negative and i is still have some value.\n\t- For example in `ros and horse` we have traversed whole `ros` and i is at `r` character so that means we have to make empty string from `hor` so we will have to perform `3 deletion operation to make it empty string`. \n\t- So if j becomes negative then we will return `i+1`.\n\n```cpp\nif(i < 0){\n\treturn j+1;\n}\nif(j < 0){\n\treturn i+1;\n}\n```\n\n## Recursive code:\n\n```cpp\nint solve(int i,int j,string &s1,string &s2){\n\tif(i < 0){\n\t\treturn j+1;\n\t}\n\tif(j < 0){\n\t\treturn i+1;\n\t}\n\tif(s1[i] == s2[j]){\n\t\treturn solve(i-1,j-1,s1,s2);\n\t}\n\telse{\n\t\treturn 1 + min(min(solve(i,j-1,s1,s2),solve(i-1,j,s1,s2)), solve(i-1,j-1,s1,s2));\n\t}\n}\n```\n\n## Memoization Code:\n\n```cpp\nint solve(int i,int j,string &s1,string &s2,vector<vector<int>>&dp){\n\tif(i < 0){\n\t\treturn j+1;\n\t}\n\tif(j < 0){\n\t\treturn i+1;\n\t}\n\tif(dp[i][j] != -1){\n\t\treturn dp[i][j];\n\t}\n\tif(s1[i] == s2[j]){\n\t\treturn dp[i][j] = solve(i-1,j-1,s1,s2,dp);\n\t}\n\telse{\n\t\treturn dp[i][j] =  1 + min(min(solve(i,j-1,s1,s2,dp),solve(i-1,j,s1,s2,dp)), solve(i-1,j-1,s1,s2,dp));\n\t}\n}\nint main(){\n\t// n is size of s1 and m is size of s2\n\tvector<vector<int>>dp(n,vector<int>(m,-1));\n\treturn solve(n-1,m-1,s1,s2,dp);\n}\n```\n\n```\nTime complexity: O(NxM)\nSpace complexity: O(NxM) + stack space of O(N+M)\n```\n\n## Tabulation Code:\n\n--> Let\'s use tabulation to remove the stack space.\n\nSo in tabulation we just have to do one smaller change which will be `we will use 1 based indexing here` because in base case we are checking if i or j becomes negative but it\'s not possible here so that\'s why we will use 1 based indexing and our dp array size will be `N+1xM+1`\n\nAlso during checking the characters we will have to check like this:\n```cpp\nif(s1[i-1] == s2[j-1]);\n```\n\nAlso in base case if `i` is 0 then we will add `j` for it instead of j+1 because we are following 1 based indexing and same for j also.\n\n```cpp\nint minDistance(string s1, string s2) {\n        int n = s1.size(),m = s2.size();\n        vector<vector<int>>dp(n+1,vector<int>(m+1,0));\n        // if j is 0\n        for(int i=0;i<=n;i++){\n            dp[i][0] = i;\n        }\n        // if i is 0\n\t\t// starting from 1 because we have already considered dp[0][0] in above loop\n        for(int j=1;j<=m;j++){\n            dp[0][j] = j;\n        }\n        for(int i=1;i<=n;i++){\n            for(int j=1;j<=m;j++){\n                if(s1[i-1] == s2[j-1]){\n                    dp[i][j] = dp[i-1][j-1];\n                }else{\n                    dp[i][j] = 1 + min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]);\n                }\n            }\n        }\n        return dp[n][m];\n    }\n```\n\n## Space optimisation:\n\n--> Here we can see that we are only required previous row(dp[i-1]) and current row (dp[i]) to find answer for current row.\n\nSo we will make 2 separate arrays `prev and curr` which will act as rows and after each inner iteration, we will swap them.\n\nNow here we can see for every `i=0` we have to put `0,1,2,3..` as j so we will initialise prev as `0,1,2,3...` and also for every `j=0` we have to put `0,1,2,3...` i.e every row\'s first element will be current index so after each inner iteration we will do `curr[0] = i`.\n\nSo let\'s optimise the space complexity:\n\n```cpp\nint minDistance(string s1, string s2) {\n\tint n = s1.size(),m = s2.size();\n\tvector<int>prev(m+1,0),curr(m+1,0);\n\tfor(int j=1;j<=m;j++){\n\t\tprev[j] = j;\n\t}\n\tfor(int i=1;i<=n;i++){\n\t// Initialising first element after each iteration\n\t\tcurr[0] = i;\n\t\tfor(int j=1;j<=m;j++){\n\t\t\tif(s1[i-1] == s2[j-1]){\n\t\t\t\tcurr[j] = prev[j-1];\n\t\t\t}else{\n\t\t\t\tcurr[j] = 1 + min(min(curr[j-1],prev[j]),prev[j-1]);\n\t\t\t}\n\t\t}\n\t\t// swapping prev and curr\n\t\tprev = curr;\n\t}\n\treturn prev[m];\n}\n```\n\n```\nTime complexity: O(NxM)\nSpace complexity: O(M)\n```\n\n----\n\nIf you want to see more solutions like this find it [here](https://github.com/shivam1317/DSA-Notes)\nThanks for reading.\n\n
['C']