Clean & Straight-forward Java Solution using Deque


  • 0

    Here is my observation, this magic string keep generating and appending itself. So I come up with a Deque solution in which the head of the queue serves as generator (1 or 2) while the tail of the queue serves as appending.

    However, somehow I notice the initial sequence 122 is a special case:

    1. The first 2 belongs to a pattern of 22, which is tricky and this is the only place. In future, if encounter a generator as 2, we can always append either double 1s or double 2s.
    2. This is the only place the Deque may be empty when poll the second 2. In future, the queue will always have more than 2 elements.

    So I will start process with 11. And the below code will speak for the rest.

        public int magicalString(int n) {
            if(n==0)
                return 0;
            if(n<=3)
                return 1;
            Deque<Integer> dq = new LinkedList<>();
            dq.offerFirst(1); dq.offerFirst(1);
            n = n-3;
            int count = 1;
            while(n-->0) {
                if(dq.pollFirst()==1) {
                    count++;
                    if(dq.peekLast()==1)
                        dq.offerLast(2);
                    else
                        dq.offerLast(1);
                } else {
                    if(dq.peekLast()==1) {
                        dq.offerLast(2);
                        dq.offerLast(2);
                    } else {
                        dq.offerLast(1);
                        dq.offerLast(1);
                    }
                }
            }
            return count;
        }

Log in to reply
 

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