Easiest Solution(DP) w/ Explanation
This is also considered as levenshtein distance algorithm. \nTime = O(mn)\nSpace = O(mn)\nHere, we can improve this method by using only 2 rows instead of the e
This is also considered as levenshtein distance algorithm. \nTime = O(mn)\nSpace = O(mn)\nHere, we can improve this method by using only 2 rows instead of the entire 2d array.\n\nHere, we have to find the minimum no of operations to convert one string to another. \nAlso, this will get harder with longer strings so our best friend here will be dynamic programming.\nWe can construct a 2d array/matrix to store all the possible least no. operations to convert one string to another.\n\n\t0 1 2 3 4\n0\n1\n2\n3\n4\n5\nWe have to initialize our matrix like this^ to add values into it. \nHere these two axis represent two strings.\nWe have taken 0 in the beginning which acts as our base case. So it will look something like this:\n       \n\t0 1 2 3 4\n0  0 0 0 0 0 \n1  0\n2  0\n3  0\n4  0\n5  0\nThis is our base case and now we\'ll just use dp to find all the values. \nOur formula will be \nif string2[i] == string1[j] # means if two letters are equal:\nmatrix[i][j] = matrix[i - 1][j - 1] because it will give us min no of operations\n\nelse:(if the letters that we\'re comparing are not equal, then well check all the values, above it, to the left if it and to the left diagonal) find min of these and add 1 to it.\n\t\t\t\t\t\t\t\t\t  \nCode:\n\n\tclass Solution:\n    def minDistance(self, word1: str, word2: str) -> int:\n        edits = [[x for x in range(len(word1) + 1)] for y in range(len(word2) + 1)] #initialize 2d\n        for i in range(1, len(word2) + 1): #initailize first column(012345)\n            edits[i][0] = edits[i - 1][0] + 1\n        for i in range(1, len(word2) + 1):\n            for j in range(1, len(word1) + 1):\n                if word2[i - 1] == word1[j - 1]: #if same just check diaginal\n                    edits[i][j] = edits[i - 1][j - 1]\n                else:\n                    edits[i][j] = 1 + min(edits[i - 1][j - 1], edits[i][j - 1], edits[i - 1][j]) #check all three vals, find min and add 1\n        return edits[-1][-1] #return final val of our 2d matrix(last row last col)\n\t\t\nIf you have any questions, feel free to comment down below. I\'m also gonna implement this using only two rows which will save some space. \n                        \n            \n        \n            \n
['Dynamic Programming', 'Matrix', 'Python', 'Python3']