Java Easy Solution || DP || Memorization
\n\n# Code\n\nclass Solution {\n    public int minimumDistance(String word) {\n        HashMap<String,Integer> cache= new HashMap<>();\n        return type(word
\n\n# Code\n```\nclass Solution {\n    public int minimumDistance(String word) {\n        HashMap<String,Integer> cache= new HashMap<>();\n        return type(word,\'\\0\', \'\\0\',0,cache);\n    }\n\n\n    int type(String word,char leftFinger,char rightFinger,int i,HashMap<String,Integer> cache){\n        if(i>=word.length())return 0;\n\n        String key=leftFinger+" "+rightFinger+" "+i;\n        if(cache.containsKey(key))return cache.get(key);\n\n        int left=distance(leftFinger,word.charAt(i))+type(word,word.charAt(i),rightFinger,i+1,cache);\n\n        int right=distance(rightFinger,word.charAt(i))+type(word,leftFinger,word.charAt(i),i+1,cache);\n        cache.put(key,Math.min(left,right));\n        return Math.min(left,right);\n    }\n\n    int distance(char prev,char curr){\n\n        if(prev==\'\\0\')return 0;\n        int x1=(prev-\'A\')/6;\n        int x2=(curr-\'A\')/6;\n        int y1=(prev-\'A\')%6;\n        int y2=(curr-\'A\')%6;\n\n         return Math.abs(x2-x1)+Math.abs(y2-y1);\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']