Simple Java solution without special cases


  • 0
    B

    Hi,

    I've read a few solutions and they all started with a precomputed sequence or treated low n (< 3) as special cases.

    I think that the beauty of my solution is that it computes the string from scratch, starting with the empty string. Then, you don't need any special treatment for low n. It just works!

    Here's the code.

    public class Solution {
        public int magicalString(int n) {
            StringBuilder sb = new StringBuilder(n);
            int count = 0; // number of 1s
            int num = 1;   // number to be added if occ != 0
            int occ = 1;   // number of occurences to be added
            int index = 1; // index of the next occurrence to be read
            while (sb.length() < n) {
                if (occ == 0) { 
                    num = 3 - num;
                    sb.append(num);
                    // Read the next number of occurrences
                    // minus the one we just wrote
                    occ = sb.charAt(index++) - '0' - 1;
                } else {
                    sb.append(num);
                    --occ;
                }
                if (num == 1) {
                    ++count;
                }
            }
            return count;
        }
    }
    

    The algorithm is simple but it requires a little trick.

    You need to write the number before reading the number of occurrences. And that's all.

    Enjoy. :)


Log in to reply
 

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