Java Topdown DP
\nclass Solution {\n    public int minimumDistance(String word) {\n        Map<String, Integer> memo = new HashMap<>();\n        return dfs(0, \'a\', \'a\', wor
```\nclass Solution {\n    public int minimumDistance(String word) {\n        Map<String, Integer> memo = new HashMap<>();\n        return dfs(0, \'a\', \'a\', word, memo);\n    }\n    int dfs(int index, char x, char y, String word, Map<String, Integer> memo) {\n        if (index == word.length()) {\n            return 0;\n        }\n        String key = index + " " + x + " " + y;\n        if (memo.containsKey(key)) {\n            return memo.get(key);\n        }\n        int res = Integer.MAX_VALUE;\n        char c = word.charAt(index);\n        int xx = (c - \'A\') / 6;\n        int yy = (c - \'A\') % 6;\n        if (x == \'a\') {\n            res = dfs(index + 1, c, y, word, memo);\n        } else {\n            int xxx = (x - \'A\') / 6;\n            int yyy = (x - \'A\') % 6;\n            int dist = Math.abs(xxx - xx) + Math.abs(yyy - yy);\n            res = dfs(index + 1, c, y, word, memo) + dist;\n        }\n        if (y == \'a\') {\n            res = Math.min(res, dfs(index + 1, x, c, word, memo));\n        } else {\n            int xxx = (y - \'A\') / 6;\n            int yyy = (y - \'A\') % 6;\n            int dist = Math.abs(xxx - xx) + Math.abs(yyy - yy);\n            res = Math.min(res, dfs(index + 1, x, c, word, memo) + dist);\n        }\n        memo.put(key, res);\n        return res;\n    }\n}\n```
[]