Java Top Down AC Solution with mem


  • 0
    S
    public class Solution {
        public int findRotateSteps(String ring, String key) {
           int[][]  mem = new int[key.length()][ring.length()];
           return helper(0,0,ring,key,mem);
        }
        
        int helper(int start, int cur, String ring, String key, int[][] mem) {
            if(start>=key.length()) {
                return 0;
            }
            if(mem[start][cur]>0) return mem[start][cur];
            if(ring.charAt(cur)==key.charAt(start)){
                mem[start][cur] = 1+helper(start+1, cur, ring, key,mem);
                return mem[start][cur];
            } else {
                //to left
                int left=0,leftcur=cur;
                while(ring.charAt(leftcur)!=key.charAt(start)){
                    left++;
                    leftcur--;
                    if(leftcur<0){
                        leftcur+=ring.length();
                    }
                }
                //to right
                int right=0,rightcur=cur;
                while(ring.charAt(rightcur)!=key.charAt(start)){
                    right++;
                    rightcur++;
                    if(rightcur>=ring.length()){
                        rightcur%=ring.length();
                    }
                }
                mem[start][cur] =  Math.min(1 + left + helper(start+1, leftcur, ring, key,mem), 1 + right + helper(start+1, rightcur, ring, key,mem));
                return mem[start][cur];
            }
        }
    }
    

Log in to reply
 

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