LeetCode Count and Say: Simulation (Java) and Mathematical Fact

Overview

LeetCode Count and Say: Simulate all the sequence by the rules and the Mathematical Fact is the count will never be larger than 4.

LeetCode Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Solution and Precautions: Simulation and Mathematical Fact

Just simulate the process until find the the n-th string, note the description it self is a bit fuzzy, count means you count the consecutive number, it is not true that there is only 1 or 2 in the string, so 1, 11, 21, 1211, 111221, the next would be 312211 because there are 3 consecutive 1 followed by 2 consecutive 2 and a single 1. And the mathematical fact behind is that the COUNT is always less than 4, one can find the formal proof online but this is not the point in this post. The following Java code implements this simulation and is accepted by LeetCode OJ to pass this Count and Say problem:

public class Solution {
    public String countAndSay(int n) {
        if (n < 1)
            return "";
        StringBuffer strBuffer = new StringBuffer("1");
        while (--n > 0) {
            int i = 0;
            int j = 0;
            int len = strBuffer.length();

            StringBuffer strNext   = new StringBuffer();
            while (j < len) {
                while (j < len &&
                       (j == i || strBuffer.charAt(j) == strBuffer.charAt(j-1)))
                    ++j;

                strNext.append(j - i);
                strNext.append(strBuffer.charAt(i));
                i = j;
            }
            strBuffer = strNext;
        }

        return strBuffer.toString();
    }
}

A final remark on the Java language detail about the conversion between char and int, my suggestion would be do not follow C/C++ style like ‘A’ + 1, since in Java ‘A’ + 1 would actually return a int value which is different from the common C/C++ interpretation. The following code illustrate this issue:

public class Tester {
    public static void main(String [] args) {
        System.out.println('B');
        System.out.println('A' + 1);
        System.out.println((char)('A' + 1));
        System.out.println("A" + 1);
    }
    // The output is as follows:
    //
    // B
    // 66
    // B
    // A1
    //
}

Summary

LeetCode Count and Say: Simulate all the sequence by the rules and the Mathematical Fact is the count will never be larger than 4.

Written on April 27, 2013