LCS [EXPLAINED] | Python | C++ | JavaScript
We can use longest common subsequence method with little bit modification.\n In LCS we only check that the corresponding letter is equal or not and according to
* We can use **longest common subsequence** method with little bit modification.\n* In **LCS** we only check that the corresponding letter is equal or not and according to it we fill out the matrix cell.\n* Here in this problem we have to perform **three types** of operations so every cell of the dp matrix will be filled out with the operation that has **minimum step**.\n* `if  word1[i-1] == word2[j-1]:`\n\t* ` dp[i][j] = dp[i][j] = dp[i-1][j-1]` means both letters are same so we don\'t need to perform any operation so number of steps will remain same as previous step.\n* `if word1[i-1] != word2[j-1]:`\n\t* case 1: we will replace the current letter of word1 with current letter of word2 --> `dp[i-1][j-1] + 1` steps.\n\t* case 2: we have reached at the end of word2 but in word1 there is an extra letter that we have to delete from word1 -->` dp[i-1][j] + 1` steps.\n\t* case 3: we have reached at the end of the word1 but there is an extra letter in word2 that we have to insert in word1 --> `dp[i][j-1] + 1` steps.\n\t* `dp[i][j] = min(case1, case2, case3)`\n--------------------\n<iframe src="https://leetcode.com/playground/XwdC88g8/shared" frameBorder="0" width="800" height="520"></iframe>\n\n-----------\n**Upvote the post if you find it helpful.\nHappy coding.**
['Dynamic Programming', 'C', 'Python', 'JavaScript']