Java Clear Solution, dfs+memoization


  • 8
    Z

    Hi There! The key point in the problem is to make decision whether to move clockwise or anticlockwise. Actually to get optimal answer, we have to move clockwise for some characters of key and anti-clockwise for others. If apply brute force, then for each position in key we have two options,

    • Search for the character clockwise
    • Search for the character anti-clockwise

    To find optimal answer we need to try both options and get minimum of them. Thus, we obtain dfs solution for the problem. But, there are duplicate calculation for some positions. Therefore, we need to memorize states. The state is defined by position of thering and the index of character in the key. This way, we can avoid calculating number of steps for the same state. Code will clarify the idea more.

    public class Solution {
        Map<String, Map<Integer, Integer>> memo;
        public int findRotateSteps(String ring, String key) {
            memo = new HashMap<>();
            return dfs(ring, key, 0);
        }
        
        private int findPos(String ring, char ch){ // find first occurrence clockwise
            return ring.indexOf(ch);
        }
        
        private int findBackPos(String ring, char ch){ //find first occurrence  anti-clockwise
            if(ring.charAt(0) == ch) return 0;
            for(int i = ring.length()-1;i>0;i--){
                if(ring.charAt(i) == ch) return i;
            }
            return 0;
        }
        
        private int dfs(String ring, String key, int i){
            if(i == key.length()) return 0;
            int res = 0;
            char ch = key.charAt(i);
            if(memo.containsKey(ring) && memo.get(ring).containsKey(i)) return memo.get(ring).get(i);
            int f = findPos(ring, ch);
            int b = findBackPos(ring, ch);
            int forward = 1+f+dfs(ring.substring(f)+ring.substring(0, f), key, i+1);
            int back = 1+ring.length()-b + dfs(ring.substring(b)+ring.substring(0, b),key, i+1);
            res = Math.min(forward, back);
            Map<Integer, Integer> ans = memo.getOrDefault(ring, new HashMap<>());
            ans.put(i, res);
            memo.put(ring, ans);
            return res;
        }
    }

  • 1
    Z

    I think your memoization may be a little bit waste of space, the state can be determined by only the 12:00 position of ring and the index of key.


  • 0
    Z

    @zzwcsong Agree:=)


  • 0
    C

    @ZhassanB How can you prove find the first occurrence of a character (clock or anti-clockwise) will yield the optimal solution?


  • 0
    Z

    @caofang I think this is a top-down approach. Assume we have already solved the first K-1 characters, then for the last character, we only need to find the closest matched character from clockwise direction and anti-clockwise direction.


  • 0
    Y
    This post is deleted!

  • 0
    Y
    This post is deleted!

  • 0
    Z

    Here is my version of DFS+memoization with comments:

    public class Solution {
        // map: for every unique char in ring, find all its occurances.
        Map<Character, Set<Integer>>map;
        
        // memo[i][j]: the min steps required when 
        // 1) the jth element of ring is at the 12:00
        // 2) the remaining key is key.substring(i)
        // this is for memorioation purpose
        int[][] memo;
        public int findRotateSteps(String ring, String key) {
            int n = ring.length(), m = key.length();
    
            map = new HashMap<>();
            for (int i=0;i<n;i++){
                char c=ring.charAt(i);
                map.putIfAbsent(c, new HashSet<>());
                map.get(c).add(i);
            }
            
            // initialize the memo: -1 represents not calculated yet.
            memo = new int[m][n];
            for (int i=0;i<m;i++)
                for (int j=0;j<n;j++)
                    memo[i][j]=-1;
            
            // "+m" is the m spelling steps 
            return helper(ring, key, 0, 0)+m;
        }
        
        private int helper(String ring, String key, int x, int y){
            if (x==key.length()) return 0;
            if (memo[x][y]>=0) return memo[x][y];
            
            int min=Integer.MAX_VALUE;
            for (int k:map.get(key.charAt(x))){
                int diff=Math.abs(k-y);
                int step=Math.min(diff, ring.length()-diff);
                min=Math.min(min, step+helper(ring, key, x+1, k));
            }
            memo[x][y]=min;
            return min;
        }
    }
    

Log in to reply
 

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