[Python] Recursion + Backtracking with explanation
IDEA1: Recursion\nI know we can solve this question by DP but I posted a recursive solution because the recursive solution is easier to think and it might be he
**IDEA1: Recursion**\nI know we can solve this question by DP but I posted a recursive solution because the recursive solution is easier to think and it might be helpful for others.\n\nMy recursive function looks like this.\n```\n# word is the input word\n# index is the word index\n# (x1, y1) is the current first finger coordinate.\n# (x2, y2) is the current second finger coordinate.\ndef recursion(self, word, index, x1, y1, x2, y2):\n\tpass\n```\n\nThere are 3 cases:\n1. Two fingers are not assigned meaning we haven\'t used fingers yet.\n2. One figer is assigned meaning we have used one finger in the previous recursion.\n3. Two fingers are assigned meanig we have used both fingers in the previous recursion.\n\nFor each case, we need to calculate the distance cost differently.\n1. We assign the first finger to word[index] w/o distance cost\n2. Two choices:\n\t* Assigning the first finger to word[index] w/ distance cost.\n\t* Assigning the second finger to word[index] w/o distance cost.\n3. Two choices:\n\t* Assigning the first finger to word[index] w/ distance cost.\n\t* Assigning the second finger to word[index] w/ distance cost.\n\nEntire code looks like this.\n```\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        return self.recursion(word, 0, -1, -1, -1, -1)\n    \n    def recursion(self, word, index, x1, y1, x2, y2):\n        if index == len(word):\n            return 0\n        \n        x, y = self.charToCoordinate(word[index])\n        if x1 == y1 == -1:\n            distance = self.recursion(word, index + 1, x, y, x2, y2)\n        elif x2 == y2 == -1:\n            distance = min(self.recursion(word, index + 1, x1, y1, x, y),\n                       self.recursion(word, index + 1, x, y, x2, y2) + self.getDistance(x1, y1, x, y))\n        else:\n            distance = min(self.recursion(word, index + 1, x, y, x2, y2) + self.getDistance(x1, y1, x, y),\n                       self.recursion(word, index + 1, x1, y1, x, y) + self.getDistance(x2, y2, x, y))\n        return distance\n    \n    def charToCoordinate(self, char):\n        position = ord(char) - ord(\'A\')\n        x = position // 6\n        y = position % 6\n        return (x, y)\n    \n    def getDistance(self, x1, y1, x2, y2):\n        return abs(x1 - x2) + abs(y1 - y2)\n```\nThis code gives Time Limit Exceeded because:\n- For each recursion, we call two recursive calls with index + 1\n- T(n) = T(n - 1) + T(n - 1) + c where n is the input word length\n- O(n^2) time and O(n) space because the depth of the recursive calls is at most n\n\n**IDEA2: Recursion + Backtracking**\nWe can reduce the complexity using a hash table with key=(index, x1, y1, x2, y2) and value=distance\n```\nclass Solution:\n    def minimumDistance(self, word: str) -> int:\n        return self.recursion(word, 0, -1, -1, -1, -1, {})\n    \n    def recursion(self, word, index, x1, y1, x2, y2, distances):\n        if index == len(word):\n            return 0\n        elif (index, x1, y1, x2, y2) in distances:\n            return distances[(index, x1, y1, x2, y2)]\n        \n        x, y = self.charToCoordinate(word[index])\n        if x1 == y1 == -1:\n            distance = self.recursion(word, index + 1, x, y, x2, y2, distances)\n        elif x2 == y2 == -1:\n            distance = min(self.recursion(word, index + 1, x1, y1, x, y, distances),\n                       self.recursion(word, index + 1, x, y, x2, y2, distances) + self.getDistance(x1, y1, x, y))\n        else:\n            distance = min(self.recursion(word, index + 1, x, y, x2, y2, distances) + self.getDistance(x1, y1, x, y),\n                       self.recursion(word, index + 1, x1, y1, x, y, distances) + self.getDistance(x2, y2, x, y))\n        distances[(index, x1, y1, x2, y2)] = distance\n        return distance\n    \n    def charToCoordinate(self, char):\n        position = ord(char) - ord(\'A\')\n        x = position // 6\n        y = position % 6\n        return (x, y)\n    \n    def getDistance(self, x1, y1, x2, y2):\n        return abs(x1 - x2) + abs(y1 - y2) \n```\nThe complexity is:\n- O(n * 26 * 26) time/space because 0 <= index < n and 26 coordinates
['Backtracking', 'Recursion', 'Memoization', 'Python']