Simple Java Recursion + Memoization (Top Down DP)


  • 0
    R
    public class Solution {
        public int findRotateSteps(String ring, String key) {
            Map<String, Integer> map = new HashMap<>();
            return stepHelper(ring, key, 0, 0, map);
        }
        
        private int stepHelper(String ring, String key, int rIndex, int kIndex, Map<String, Integer> map) {
            if(kIndex == key.length()) {
                return 0;
            }
            
            char c = key.charAt(kIndex);
            String k = rIndex + ","+ kIndex;
            if(map.containsKey(k)) {
                return map.get(k);
            }
            
            int cClock = 1, i = rIndex;
            while(true) {
                if(ring.charAt(i) == c) {
                    break;
                } else {
                    cClock++;
                    i = (i + 1) % ring.length();
                }
            }
            
            int cAClock = 1, j = rIndex;
            while(true) {
                if(ring.charAt(j) == c) {
                    break;
                } else {
                    cAClock++;
                    j = (j - 1 + ring.length()) % ring.length();
                }
            }
            
            int count = Math.min(cClock + stepHelper(ring, key, i, kIndex + 1, map), 
                                    cAClock + stepHelper(ring, key, j, kIndex + 1, map));
            map.put(k, count);
            return count;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.