[Java] DP Solution with detailed written & video explanation
Explanation : \n1. We store using a map of each character for the coordinate on the keyboard\n2. Key of the memoization will be position of (Finger1, Finger2, I
Explanation : \n1. We store using a map of each character for the coordinate on the keyboard\n2. Key of the memoization will be position of (Finger1, Finger2, Index Position of the word)\n\nExtra optimization(not implemented) : Finger1 and Finger2 can be a set to reduce number of repetitive computation as well\nsince Finger1(x=2,y=3), Finger2(x=5,y=7) will be equivalend as Finger2(x=2,y=3), Finger1(x=5,y=7)\n\n<iframe width="560" height="315" src="https://www.youtube.com/embed/h9UH-ZZMy_8" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>\n\n```\nclass Solution {\n    \n    int distance(int[] f1, int[] f2) {\n        if(f1 == null || f2 == null) {\n            return 0;\n        }\n        return Math.abs(f1[0] - f2[0]) + Math.abs(f1[1] - f2[1]);\n    }\n    \n    Map<Character, int[]> keyMap = new HashMap<>();\n    Map<String, Integer> dpCache = new HashMap<>();\n    \n    public int minimumDistance(String word) {\n        char curr = \'A\';\n        for(int i = 0; i < 5; i++) {\n            for(int j = 0; j < 6; j++) {\n                keyMap.put(curr, new int[]{i, j});\n                if(curr == \'Z\') break;\n                curr++;\n            }\n        }\n        return solve(null, null, 0, word);\n    }\n    \n    int solve(int[] f1, int[] f2, int index, String word) {\n        if(index >= word.length()) return 0;\n        \n        String key = Arrays.toString(f1) + ";" + Arrays.toString(f2) + ";" + index; \n        if(dpCache.containsKey(key)) return dpCache.get(key);\n        int f1Use = distance(f1, keyMap.get(word.charAt(index))) \n            + solve(keyMap.get(word.charAt(index)), f2, index + 1, word);\n        int f2Use = distance(f2, keyMap.get(word.charAt(index)))\n            + solve(f1, keyMap.get(word.charAt(index)), index + 1, word);\n        int output = Math.min(f1Use, f2Use);\n        dpCache.put(key, output);\n        return output;\n    }\n    \n}\n```
[]