Most easy understandable solution with detail explaination


  • 0
    S
    //Fast Solution : DP
    //Transition Formula: dp[i][j] = Math.min(dp[i + 1][k1] + clockStep(k1, j), dp[i + 1][k2] + antiStep(k2, j));
    //Time: O(m*n) 46 ms, 86%
    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int m = key.length();
        int[][] dp = new int[m + 1][n];
        int[][] clock = preproc(ring, 1), anti = preproc(ring, -1);
        for (int i = m - 1; i >= 0; i--) {
            int idx = key.charAt(i) - 'a';
            for (int j = 0; j < n; j++) {
                int k1 = clock[j][idx];
                int k2 = anti[j][idx];
                dp[i][j] = Math.min(dp[i + 1][k1] + (j - k1 + n) % n, dp[i + 1][k2] + (k2 - j + n) % n);
            }
        }
        
        return dp[0][0] + m;
    }
    int[][] preproc(String r, int inc) {
        int n = r.length();
        int[][] ans = new int[n][26];
        int[] map = new int[26];
        for (int i = 0, j = 0; j < n * 2 - 1; ++j) {
            map[r.charAt(i) - 'a'] = i;
            for (int k = 0; k < 26; k++) {
                ans[i][k] = map[k];
            }
            i = (i + inc + n) % n;
        }
        return ans;
    }
    
    //Solution: DFS + Memo
    
    public int findRotateSteps(String ring, String key) {
         Map<String, Integer> memo = new HashMap<>();
        return dfs(memo, ring, key, 0);
    }
    
    //memo: key is ring & index as a string, value is min steps;
    //index: is index of key
    private int dfs(Map<String, Integer> memo, String ring, String key, int index) {
        if (index >= key.length()) {
            return 0;
        }
        
        //Fetch memory
        String memoKey = ring + index;
        if (memo.containsKey(memoKey)) {
            return memo.get(memoKey);
        }
        
        //DFS
        char c = key.charAt(index);
        int forwardPos = getPosition(ring, c);//forward position
        int backwardPos = getBackPosition(ring, c);//backward position
    
        //forward steps and backward steps
        int forwardSteps = 1 + forwardPos 
            + dfs(memo, ring.substring(forwardPos) + ring.substring(0, forwardPos), key, index + 1); 
        int backwardSteps = 1 + ring.length() - backwardPos 
            + dfs(memo, ring.substring(backwardPos) + ring.substring(0, backwardPos), key, index + 1);
        int steps = Math.min(forwardSteps, backwardSteps);
        
        //Memorize
        memo.put(memoKey, steps);
        
        return steps;
    }
    
    private int getPosition(String ring, char c) {
        return ring.indexOf(c);
    }
    
    private int getBackPosition(String ring, char c) {
        return ring.length() - 1 - new StringBuffer(ring).reverse().toString().indexOf(c);
    }

  • 0
    S

    Best DP solution.


  • 0
    S

    Easy understandable DFS solution.


Log in to reply
 

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