Python solutions and intuition
For those having difficulty cracking dynamic programming solutions, I find it easiest to solve by first starting with a naive, but working recursive implementat
For those having difficulty cracking dynamic programming solutions, I find it easiest to solve by first starting with a naive, but working recursive implementation. It\'s essential to do so, because dynamic programming is basically recursion with caching. With this workflow, deciphering dynamic programming problems becomes just a little more manageable for us normal people. :)\n\n**Thought process:**\nGiven two strings, we\'re tasked with finding the minimum number of transformations we need to make to arrive with equivalent strings. From the get-go, there doesn\'t seem to be any way around trying all possibilities, and in this, possibilities refers to inserting, deleting, or replacing a character. Recursion is usually a good choice for trying all possilbilities. \n\nWhenever we write recursive functions, we\'ll need some way to terminate, or else we\'ll end up overflowing the stack via infinite recursion. With strings, the natural state to keep track of is the index. We\'ll need two indexes, one for word1 and one for word2. Now we just need to handle our base cases, and recursive cases. \nWhat happens when we\'re done with either word? Some thought will tell you that the minimum number of transformations is simply to insert the rest of the other word. This is our base case. What about when we\'re not done with either string? We\'ll either match the currently indexed characters in both strings, or mismatch. In the first case, we don\'t incur any penalty, and we can continue to compare the rest of the strings by recursing on the rest of both strings. In the case of a mismatch, we either insert, delete, or replace. To recap:\n1. base case: word1 = "" or word2 = "" => return length of other string\n2. recursive case: word1[0] == word2[0] => recurse on word1[1:] and word2[1:]\n3. recursive case: word1[0] != word2[0] => recurse by inserting, deleting, or replacing \n\nAnd in Python:\n```\nclass Solution:\n    def minDistance(self, word1, word2):\n        """Naive recursive solution"""\n        if not word1 and not word2:\n            return 0\n        if not word1:\n            return len(word2)\n        if not word2:\n            return len(word1)\n        if word1[0] == word2[0]:\n            return self.minDistance(word1[1:], word2[1:])\n        insert = 1 + self.minDistance(word1, word2[1:])\n        delete = 1 + self.minDistance(word1[1:], word2)\n        replace = 1 + self.minDistance(word1[1:], word2[1:])\n        return min(insert, replace, delete)\n```\n\nWith a solution in hand, we\'re ecstatic and we go to submit our code. All is well until we see the dreaded red text... **TIME LIMIT EXCEEDED**. What did we do wrong? Let\'s look at a simple example, and for sake of brevity I\'ll annotate the minDistance function as ```md```. \n\nword1 = "horse"\nword2 = "hello"\n\nThe tree of recursive calls, 3 levels deep, looks like the following. I\'ve highlighted recursive calls with multiple invocations. So now we see that we\'re repeating work. I\'m not going to try and analyze the runtime of this solution, but it\'s exponential. \n\n```\nmd("horse", "hello")\n\tmd("orse", "ello")\n\t\tmd("orse", "llo")\n\t\t\tmd("orse", "lo")\n\t\t\tmd("rse", "llo") <- \n\t\t\tmd("rse", "lo")\n\t\tmd("rse", "ello")\n\t\t\tmd("rse", "llo") <-\n\t\t\tmd("se", "ello")\n\t\t\tmd("se", "llo") <<-\n\t\tmd("rse", "llo")\n\t\t\tmd("rse", "llo") <-\n\t\t\tmd("se", "llo") <<-\n\t\t\tmd("se", "lo")\n```\n\nThe way we fix this is by **caching**. We save intermediate computations in a dictionary and if we recur on the same subproblem, instead of doing the same work again, we return the saved value. Here is the memoized solution, where we build from bigger subproblems to smaller subproblems (top-down).\n```\nclass Solution:\n    def minDistance(self, word1, word2, i, j, memo):\n        """Memoized solution"""\n        if i == len(word1) and j == len(word2):\n            return 0\n        if i == len(word1):\n            return len(word2) - j\n        if j == len(word2):\n            return len(word1) - i\n\n        if (i, j) not in memo:\n            if word1[i] == word2[j]:\n                ans = self.minDistance2(word1, word2, i + 1, j + 1, memo)\n            else: \n                insert = 1 + self.minDistance2(word1, word2, i, j + 1, memo)\n                delete = 1 + self.minDistance2(word1, word2, i + 1, j, memo)\n                replace = 1 + self.minDistance2(word1, word2, i + 1, j + 1, memo)\n                ans = min(insert, delete, replace)\n            memo[(i, j)] = ans\n        return memo[(i, j)]\n```\n\nOf course, an interative implementation is usually better than its recursive counterpart because we don\'t risk blowing up our stack in case the number of recursive calls is very deep. We can also use a 2D array to do essentially the same thing as the dictionary of cached values. When we do this, we build up solutions from smaller subproblems to bigger subproblems (bottom-up). In this case, since we are no longer "recurring" in the traditional sense, we initialize our 2D table with base constraints. The first row and column of the table has known values since if one string is empty, we simply add the length of the non-empty string since that is the minimum number of edits necessary to arrive at equivalent strings. For both the memoized and dynamic programming solutions, the runtime is ```O(mn)``` and the space complexity is ```O(mn)``` where m and n are the lengths of word1 and word2, respectively.\n```\nclass Solution:\n    def minDistance(self, word1, word2):\n        """Dynamic programming solution"""\n        m = len(word1)\n        n = len(word2)\n        table = [[0] * (n + 1) for _ in range(m + 1)]\n\n        for i in range(m + 1):\n            table[i][0] = i\n        for j in range(n + 1):\n            table[0][j] = j\n\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if word1[i - 1] == word2[j - 1]:\n                    table[i][j] = table[i - 1][j - 1]\n                else:\n                    table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])\n        return table[-1][-1]\n```\n\n
[]