Count and Say

Question: The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

You may find the full question here.

Approach: Let’s start with something simple and probably less efficient.

//Approach
//Runtime: 7ms
//Memory usage: 37.5MB
class Solution {
    public String countAndSay(int n) {
        String currNumber = "1";
        char[] charArray;
        int currIndex = 0;
        char currChar;
        for(int i = 2; i<=n; i++){
            //Re-initialize
            charArray = currNumber.toCharArray();
            currNumber = "";
            currIndex = 0;
            while(currIndex<charArray.length){
                int count = 1;
                currChar = charArray[currIndex++];
                for(; currIndex<charArray.length; currIndex++){
                    if(charArray[currIndex]!=currChar){
                        break;
                    }
                    count++;
                }
                currNumber = currNumber + count + currChar;
            }
        }
        return currNumber;
    }
    
}

You can check out a slightly modified version of this problem here.

Find more posts here.

Cheers & Chao!