[Java] Brute Recursion + Memoization
The state of the sub-problem depends on the position of the fingers and the index of the string till which you have typed. \n From the state, you will be able t
* The state of the sub-problem depends on the position of the fingers and the index of the string till which you have typed. \n* From the state, you will be able to find the dimensionality of the problem.\n* Any sub-problem can be uniquely identified from the x co-ordinate of finger1, y co-ordinate of finger 1, x co-ordinate of finger 2, y co-ordinate of finger 2 and the index of the string(word) till which you have typed, so you can store the answer to this sub-problem in the 5D array or any other data structure so that, if you come across it again, you can fetch it in O(1) time.\n\n\nThe solution can be improved by combining the x and y co-ordinates of the two fingers separately.\n```\nclass Solution {\n    public static int function(String word, int n, int i, int f1x, int f1y, int f2x, int f2y, HashMap<Character, String> map, int[][][][][] dp) {\n        if(i == n) return 0;\n        if(dp[i][f1x][f1y][f2x][f2y] != -1) return dp[i][f1x][f1y][f2x][f2y];\n        char curr = word.charAt(i);\n        int currRow = map.get(curr).charAt(0) - \'0\';\n        int currColumn = map.get(curr).charAt(1) - \'0\';\n        int p1 = 0, p2 = 0;\n        if(f1x != 5 || f1y != 5) p1 += Math.abs(f1x - currRow) + Math.abs(f1y - currColumn);\n        if(f2x != 5 || f2y != 5) p2 += Math.abs(f2x - currRow) + Math.abs(f2y - currColumn);\n        p1 += function(word, n, i + 1, currRow, currColumn, f2x, f2y, map, dp);\n        p2 += function(word, n, i + 1, f1x, f1y, currRow, currColumn, map, dp);\n        return dp[i][f1x][f1y][f2x][f2y] = Math.min(p1, p2);\n    }\n    public int minimumDistance(String word) {\n        int n = word.length();\n        HashMap<Character, String> map = new HashMap<>();\n        int[][][][][] dp = new int[n][6][6][6][6];\n        for(int l = 0; l < n; l++) {\n                for(int i = 0; i < 6; i++) {\n\t\t\t\t\tfor(int j = 0; j < 6; j++) {\n\t\t\t\t\t\tfor(int t = 0; t < 6; t++) {\n\t\t\t\t\t\t\tfor(int p = 0; p < 6; p++) dp[l][i][j][t][p] = -1;\n\t\t\t\t\t\t}\n\t\t\t\t\t}\n            }\n        }\n        for(int i = 0; i < 26; i++) {\n            char curr = (char)(65 + i);\n            int r = (i % 6), c = (i / 6); \n            map.put(curr, Integer.toString(r) + Integer.toString(c));\n        }\n        return function(word, n, 0, 5, 5, 5, 5, map, dp);\n    }\n}
[]