Python Solution BFS with Comments
First we use finger1 to type first character\nthen when we type following characters from left to right, we have two choices for each type, finger1 or finger2.\
First we use finger1 to type first character\nthen when we type following characters from left to right, we have two choices for each type, finger1 or finger2.\nUse BFS to solve this question. Traverse from left to right, and for each character update the last position for finger1 and finger2\nTake cake as an example, pop ["C", "None", 0] from the q, then append [A, None, 2] (type with finger1), [C, A, 0] (type with finger2) back to the q.\n\nI think the most import thing is, in BFS, dictionary should be used to avoid redundency., because many cases can end up with the same last positions. In this case, we remain the shortest distance \n\n\n```\ndef minimumDistance(self, word: str) -> int:\n        q = []\n        \n        # use q to store :\n\t\t# [the last position of finger1, the last position of finger2, the number of distance until current type] \n        \n        keyboard = {"A": (0, 0), "B": (0, 1), "C": (0, 2), "D":(0, 3), "E": (0, 4), "F": (0, 5),\n                  "G": (1, 0), "H":(1, 1), "I": (1, 2), "J":(1, 3), "K": (1, 4), "L": (1, 5),\n                  "M": (2, 0), "N": (2, 1), "O": (2, 2), "P":(2, 3), "Q": (2, 4), "R": (2, 5),\n                  "S": (3, 0), "T": (3, 1), "U": (3, 2), "V":(3, 3), "W": (3, 4), "X": (3, 5),\n                  "Y": (4, 0), "Z": (4, 1)}\n        \n        q = [[word[0], None, 0]]\n        \n        # first let finger1 to type the first character  put the [word[0], None, 0] into q\n\t\t\n        for w in word[1:]:\n            dic = {}\n\t\t# since there are some cases with the same last positions, so we use dictionary to reduce redundancy.\n\t\t# there are two cases on each steps. Type with finger one or finger two.\n            while q:\n                last = q.pop()\n                last1 = last[0]                       \n                last2 = last[1]\n                n = last[2]\n                w_last_1 = abs(keyboard[last1][0] - keyboard[w][0]) + abs(keyboard[last1][1] - keyboard[w][1])\n                if last2:\n                    w_last_2 = abs(keyboard[last2][0] - keyboard[w][0]) + abs(keyboard[last2][1] - keyboard[w][1])\n                else:\n                    w_last_2 = 0\n\t\t\t\t# update the last positions and the distances\n                if (w, last2) not in dic:\n                    dic[(w, last2)] = n + w_last_1\n                else: \n                    dic[(w, last2)] = min(dic[(w, last2)], n + w_last_1)\n                if (last1, w) not in dic:\n                    dic[(last1, w)] = n + w_last_2\n                else: \n                    dic[(last1, w)] = min(dic[(last1, w)], n + w_last_2)\n            for k in dic.keys():\n                q.append([k[0], k[1], dic[k]])\n           \n        res = float("inf")\n        for i in q:\n            res = min(res, i[2])\n        return res
[]