O(N*27*27) MEMOIZED JAVA SOLUTION WITH EXPLANATION
\t// time and space complexity : O(n * 27 27)\n\t/\n\t  1)Assuming the position as a 2D grid would lead to much higher dimensions dp table.\n\t  2)Instead we wi
\t// time and space complexity : O(n * 27 *27)\n\t/*\n\t  1)Assuming the position as a 2D grid would lead to much higher dimensions dp table.\n\t  2)Instead we will mark code for each character, Like \'A\' -> 1, \'B\' -> 2 , \'G\' -> 7 .... \'Z\' -> 26\n\t  3)So instead of having x and y corrdinates for each finger, we will represents each finger by these codes.\n\t  4)For a code ,we can easily find out its respective position in 2D grid for calculating distance btw 2 consecutive characters of word .\n\t  5) After this, finger1 and finger2 have value in range [0,26] denoting previously typed character by them. finger2==0 means finger 2 has not been used yet.\n\t  6) If finger2 has not been used yet, we have 2 options, either to start using finger2 or we use of finger1 to type current character.\n\t  7) When both fingers are used previously, we have 2 choices either to use finger1 to type current character or use finger 2\n\n\t*/\n\tclass Solution {\n\t\tint[][][] dp;\n\t\tpublic int minimumDistance(String str) {\n\t\t\tdp = new int[str.length()][27][27];\n\t\t\tfor(int i=0;i<dp.length;i++)\n\t\t\t\tfor(int j=0;j<27;j++)\n\t\t\t\t\tArrays.fill(dp[i][j],-1);\n\t\t\treturn helper(str,1,str.charAt(0)-\'A\'+ 1,0);\n\n\t\t}\n\t\tprivate int helper(String str,int i,int finger1,int finger2){\n\t\t\tif(i==str.length())return 0;\n\t\t\tif(dp[i][finger1][finger2]!=-1)return dp[i][finger1][finger2];\n\t\t\tint ch = str.charAt(i) - \'A\' + 1;\n\t\t\tif(finger2==0){\n\t\t\t\tint c1 = helper(str,i+1,finger1,ch);    // start using finger 2\n\t\t\t\tint c2 = distance(ch,finger1) + helper(str,i+1,ch,finger2);   // finger 1 is used\n\t\t\t\treturn  dp[i][finger1][finger2] = Math.min(c1,c2);\n\t\t\t}\n\t\t\tint c1 = distance(ch,finger1) + helper(str,i+1,ch,finger2);   // finger 1 is used\n\t\t\tint c2 = distance(ch,finger2) + helper(str,i+1,finger1,ch);    // finger 2 is used\n\t\t\treturn  dp[i][finger1][finger2] = Math.min(c1,c2);\n\t\t}\n\t\tprivate int distance(int a,int b){\n\t\t\tint ax = (a-1)/6;\n\t\t\tint bx = (b-1)/6;\n\t\t\tint ay = (a-1)%6;\n\t\t\tint by = (b-1)%6;\n\t\t\treturn Math.abs(ax-bx) + Math.abs(ay-by);\n\t\t}\n\t}\n
[]