Java DP, easy to understand with explanation


  • 0
    public class Solution {
        public int findRotateSteps(String ring, String key) {
            int len = key.length();
            //With current steps, the max number of chars can spell when stop at ring[i]
            int[] dp = new int[ring.length()];
            Arrays.fill(dp, -1); //-1 means can not be reached
            int step = 0;
            dp[0] = 0; //start position
            while(true) {
                step++;
                int[] next = new int[ring.length()];
                Arrays.fill(next, -1);
                for(int i=0; i<dp.length; i++){
                    if(dp[i]<0){
                        continue; //can not reach current position
                    }    
                    int left = i-1>=0? i-1 : dp.length-1;
                    next[left] = Math.max(next[left], dp[i]); //move left from i
                    int right = i+1<dp.length? i+1 : 0;
                    next[right] = Math.max(next[right], dp[i]); //move right from i
                    if(ring.charAt(i) == key.charAt(dp[i])){ //spell current char
                        dp[i]++;
                        if(dp[i] == len) return step;
                        next[i] = Math.max(next[i], dp[i]);
                    } 
                    // no else, since if it's not a match, we won't stay
                }
                dp = next;
            }
        }
    }
    

Log in to reply
 

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