Share my DP solution with explanation


  • 0
    Z

    We can use (the last char in key matched, the according char index in ring) as the dp state. As we go to the next char in key, we can go through each previous state, find a valid one, and calculate a minimum result when an index is fixed. Since for a single char, there can be multiple valid indices pointing to it, we will get the final result by running a final for loop. Thanks to @shawngao for the inspiration for steps calculation. It's really brilliant.

    dp(next char, j') = min(dp(previous char, j1), dp(previous char, j2), ... , dp(previous char, jk))

    public class Solution {
        public int findRotateSteps(String ring, String key) {
            int n = ring.length();
            int m = key.length();
            int[][] dp = new int[m + 1][n];
            
            dp[0][0] = 0;
            for(int j = 1; j < n; j++) {
                dp[0][j] = -1;
            }
            
            for(int i = 1; i <= m; i++) {
                for(int jp = 0; jp < n; jp ++) {
                    if(ring.charAt(jp) == key.charAt(i - 1)) {
                        dp[i][jp] = Integer.MAX_VALUE;
                        for(int j = 0; j < n; j++) {
                            if(-1 < dp[i - 1][j]) {
                                int diff = Math.abs(jp - j);
                                int step = Math.min(diff, n - diff);
                                dp[i][jp] = Math.min(dp[i][jp], dp[i - 1][j] + step);
                            }
                        }
                    }
                    else {
                        dp[i][jp] = -1;
                    }
                }
            }
            
            int res = Integer.MAX_VALUE;
            for(int j = 0; j < n; j++) {
                if(dp[m][j] > -1) {
                    res = Math.min(res, dp[m][j]);
                }
            }
            
            return res + m;
        }
    }
    

Log in to reply
 

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