[python] Detailed comments using Dijkstra
\nclass Solution(object):\n    def minimumDistance(self, word):\n        """\n        :type word: str\n        :rtype: int\n        """\n        def locate(grid
```\nclass Solution(object):\n    def minimumDistance(self, word):\n        """\n        :type word: str\n        :rtype: int\n        """\n        def locate(grid, c):\n            for i in xrange(len(grid)):\n                for j in xrange(len(grid[i])):\n                    if grid[i][j] == c:\n                        return (i, j)\n                    \n        def manhattan_dist(u, v):\n            if u == None or v == None:\n                return 0\n            return abs(u[0] - v[0]) + abs(u[1] - v[1])\n           \n        # Mundane setup work so we can look up the location of each character on the board quickly\n        grid = [list(\'ABCDEF\'), list(\'GHIJKL\'), list(\'MNOPQR\'), list(\'STUVWX\'), list(\'YZ\')]\n        loc = {}\n        for c in set(word):\n            loc[c] = locate(grid, c)\n        \n        # Imagine having the position of the two fingers, A and B, and word[i] just typed out,\n        # as some state (p_a, p_b, i). At each state we have the options of changing either \n        # position p_a or p_b to the position of the next character to be typed out, word[i+1].\n\t\t# Moving finger A results in the next state (loc[word[i+1]], p_b, i + 1), moving finger B \n\t\t# results in the next state (p_a, loc[word[i+1]], i + 1). The cost of changing is the \n\t\t# manhattan_dist from p_a to word[i+1] or p_b to word[i+1]. Therefore we could imagine\n\t\t# modeling this as a graph where the states are nodes in the graph, the edges the\n        # possible transitions from one state to another, and the weight of an edge the \n        # manhattan_dist from one state to the next due to moving one of the fingers. \n        # With that in mind, we can run the standard Dijkstra algorithm over the graph!\n        \n        # Starting position where both fingers are "free", modeled as None and no character\n        # has been typed, modeled as -1. The goal is to reach some state (p_a, p_b, len(words)-1)\n        # with the cheapest path cost.\n        start = (None, None, -1)\n        d = {}\n        d[start] = 0\n        \n        q = []\n        heapq.heappush(q, [0, start])\n        while len(q) > 0:\n            ds, u = heapq.heappop(q)\n            if u in d and d[u] != ds:\n                continue\n            \n            # i points to the character we\'ve just typed\n            p_a, p_b, i = u\n            if i == len(word) - 1:\n                # We just typed out the last character, ds by Dijkstra must be the min path\n                # cost from start\n                return ds\n            \n            # To type out the next letter, we could move finger_a or finger_b with the cost\n            # based on the manhattan_dist between that finger and the next letter. We\'ll model\n            # that as an edge with the weight of the said cost\n            i = i + 1\n            next_loc_finger_a = (loc[word[i]], p_b, i)\n            cost_moving_finger_a = manhattan_dist(p_a, loc[word[i]])\n            next_loc_finger_b = (p_a, loc[word[i]], i)\n            cost_moving_finger_b = manhattan_dist(p_b, loc[word[i]])\n            nbs = [(next_loc_finger_a, cost_moving_finger_a), (next_loc_finger_b, cost_moving_finger_b)]\n            for nb in nbs:\n                v, cost = nb\n                if v not in d or d[v] > d[u] + cost:\n                    d[v] = d[u] + cost\n                    heapq.heappush(q, [d[v], v])\n        \n        # Never reached as we are guranteed to hit the character words[len(words)-1]\n        return 0\n```
[]