Clear DFS + Memorization solution in Java


  • 0
    H

    A naive DFS solution will lead to TLE. So we need a better solution. In the naive DFS, there are many duplicate computations, so we can use a 2D array, let's say it is called dp, to store the answers we have already known. For the dp array, dp[i][j] represents the best solution we can have for starting at index j in string key, if we use the ith element from string ring. Here is the code below:

    public class Solution {

    public int findRotateSteps(String ring, String key) { // DFS solution
        Map<Character, List<Integer>> map = new HashMap<>();
        char[] chs = ring.toCharArray();
        char[] ks = key.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            if (!map.containsKey(chs[i])) map.put(chs[i], new ArrayList<Integer>());
            map.get(chs[i]).add(i);
        }
        int[][] dp = new int[ring.length()][key.length()];
        return dfs(ks, chs.length, 0, map, 0, 0, dp);
    }
    
    private int dfs(char[] ks, int length, int index, Map<Character, List<Integer>> map, int steps, int cur, int[][] dp) {
        if (index < ks.length && dp[cur][index] != 0) return steps + dp[cur][index];
        if (index == ks.length) {
            return steps;
        }
        
        List<Integer> next = map.get(ks[index]);
        int min = Integer.MAX_VALUE;
        for (int i : next) {
            int clock, cClock;
            if (i > cur) {
                clock = cur + length - i;
                cClock = i - cur;
            }else {
                clock = cur - i;
                cClock = length - cur + i;
            }
            int goClock = dfs(ks, length, index + 1, map, steps + clock + 1, i, dp); // go clockwise
            int goCClock = dfs(ks, length, index + 1, map, steps + cClock + 1, i, dp); // go counterclockwise
            min = Math.min(min, Math.min(goClock, goCClock));
        }
        
        dp[cur][index] = min - steps; /* store the value for starting from index if we use cur from string ring*/
        return min;
    }
    

    }


Log in to reply
 

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