Simple Solution Java DFS memorization
Simply we try to click on the characters of the word using either finger and check which path was cheeper.\nTime complexity i think is going to be O(N * N) wher
Simply we try to click on the characters of the word using either finger and check which path was cheeper.\nTime complexity i think is going to be O(N * N) where N is the length the word and the memory is the same.\n\n```\nclass Solution {\n    int cache[][];\n    public int minimumDistance(String word) {\n        char[] arr = word.toCharArray();\n        // adding one to the size to save the state of finger being off keyboard in index 0\n\t\t// every other cache element is shifted by 1\n        cache = new int[arr.length +1] [arr.length +1];\n        for(int i = 0 ; i < arr.length; i++) {\n            Arrays.fill(cache[i], -1);\n        }\n        return  dfs(0, -1 , arr, 1);\n    }\n\n    public int dfs(int c, int c2 , char[] arr, int next) {\n       if(next >= arr.length ) {\n            return 0;\n        }\n        \n        if(cache[c+1][c2+1] != -1) {\n            return cache[c + 1][c2 +1];\n        }\n        \n        int s1 = Integer.MAX_VALUE, s2 = Integer.MAX_VALUE;\n        // Either use first finger for the next character\n        s1 = dfs(next, c2 , arr, next + 1) + getCost(c, next, arr);  \n        // use the second finger for the next character\n        s2 = dfs(c, next, arr,  next +1) + getCost(c2, next, arr);     \n        \n        cache[c + 1][c2 + 1] = Math.min(s1,s2);\n        return cache[c + 1][c2 + 1];\n    }\n    \n    public int getCost(int c, int c2, char[] arr) {\n        // c == -1 if finger was off the keyboard\n        if( c == -1 || c2 == -1) {\n            return 0;\n        }\n\t\t// this is taken from @rickyl22 solution\n\t\t/*\n\t\thttps://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/discuss/477762/Java-DP-easy-to-understand-with-explanation\n\t\t*/\n        int source = arr[c] - \'A\';\n        int target = arr[c2] - \'A\';\n        if(source == 26) return 0;\n        int y = source / 6;\n        int x = source % 6;\n        int y2 = target / 6;\n        int x2 = target % 6;\n        return Math.abs(y2-y) + Math.abs(x2-x);\n    }\n\n}\n```
[]