Java Easy understanding solution! Recursion + memorization


  • 2

    The state is represented by the 12:00 direction of index p and the current index of key to spell.
    Initially, p = 0. Rotate both direction to find the character to match the character in key to spell. there are two cases:

    1. left rotation and right rotation end up with same index (i==j) then there is only one branch
    2. they end up with different index then there are two branch
      Below is the code please feel free to advise
        public int findRotateSteps(String ring, String key) {
            if(ring.length()==0 || key.length()==0) return 0;
            return findShortest(ring.toCharArray(), 0, key.toCharArray(), 0, new int[ring.length()][key.length()]);
        }
        private int findShortest(char[] arr, int p,  char[] key, int idx, int[][] mem) {
            if(idx==key.length) return 0;
            if(mem[p][idx]>0) return mem[p][idx];
            int c1 = 0, c2=0,i=p, j=p;
            for(; arr[i]!=key[idx]; c1++) {
                i=(i+1)%arr.length;
            }
            for(; arr[j]!=key[idx];c2++) {
                j=(j-1+arr.length)%arr.length;
            }
            if(i==j) { //rotate to same location then use the less count one
                mem[p][idx]= Math.min(c1,c2)+1 + findShortest(arr, i, key, idx+1, mem);
            } else {
                int r1 = findShortest(arr, i, key, idx+1, mem) + c1 + 1;
                int r2 = findShortest(arr, j, key, idx+1, mem) + c2 + 1;
                mem[p][idx] = Math.min(r1,r2);
            }
            return mem[p][idx];
        }

  • 0
    Z

    I find your solution is straightforward. Not sure why someone downvoted this answer.


  • 1
    Z

    I have an idea to optimize the code, instead of searching the index by loop through the ring in both clockwise or anti-clockwise direction, we can preprocessing all the characters. We can have a HashMap<Character, TreeSet<Integer>> to record all the characters‘ index with treeset. Then we can use TreeSet's floor() and ceiling() to get its closest element in O(logk) time instead of O(R) (R = |ring|) time previously, where k is the number of the duplicate elements for that character. Preprocessing would take at worst O(RlogR) time.

    Let's say for character 'd', ring's length is R = 10, 'd' exists in indices 0, 1, 2, 4, 7. If our current position is 6, we can compare it with only 4 and 7. if our current position is 8, it's a little bit tricky, we want to compare it with both 7 and 0.
    To solve the second cycling issue, we can additionally put a 10 into TreeSet, and mod R when we actually use it as index.


  • 1

    @zzwcsong Thanks! I don't know why :). Lets' do a time complexity
    analysis. Let m be the length of ring and n be the length of key. This
    is actually top down approach of dynamic programming, where we can
    calculate the time complexity as # of subproblem X time-per-sub. The
    number of subproblems is bounded by length of key (n) (Edit--- I actually not quite certain about it after rethinking it, but definitely bounded by nm), since each
    character in key we at most search two directions each time, so the time
    to solve a subproblem is 2m, so the total time complexity is O(m^2n).

    Another difference in this solution is that greedy approach is applied
    here. In other upvoted DP, they check every occurrence in ring of each character
    in key which I think is unnecessary because the closest match in a direction will dominate other occurrences.
    So we only need to check the closest one in two directions not every duplicates.
    If If there is only one appearance then both direction end with same location.

    This is a Google interview problem because I found the original post of this problem posted here. If you look at the original problem, there are 3 different condition and this problem is the last condition.
    https://discuss.leetcode.com/topic/64289/freedom-trail

    1. rotate only one direction no duplicates
    2. can rotate two directions no duplicates
    3. two directions and has duplicates

    After consider the three conditions one by one I think the problem is clearer.


  • 0

    @zzwcsong That's a good suggestion. we may improve the time complexity to O(nmlogm). It's good to discuss with you:)


  • 0

    @zzwcsong After think a bit more I may get wrong about the number of subproblems, it should be over than length of key. but I still believe it is faster than regular DP because the gready approach.


  • 0

    nice clean solution


Log in to reply
 

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