Count and Say Cont…

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 2: The usual promise of a follow-up post is to enhance the performance, but clearly I have somehow managed to worsen the already lousy performance as seen in the previous post.

Let’s quickly discuss the idea behind this code. (Honestly, it was never intended to be this lousy and inefficient.) Let’s get to the logic now —

• The starting point for us is to understand that, the pattern never changes. The result for countAndSay(1) will always be “1”, and for countAndSay(5) will always be “111221”.
• To compute the pattern for n, it appears that we need to have the pattern for n-1 already handy.
• We can effectively break down the implementation into two parts. One that is used to do the actual computation of the string pattern. And two, that stores the computed pattern for future reference. In this code, we using a HashMap to store the pattern values. This way, if we already have the patterns up to 5 in the map and the goal is to find the pattern for 8; we can directly start from the pattern for 5 as the base and not all the way from 1.

//Approach 2
//Runtime 8ms
class Solution {
    static HashMap<Integer, String> map = new HashMap<>();
    static int hasValueTill = 1;
    {
 map.put(1, "1");
 }
    public String countAndSay(int n) {
     if(n<=hasValueTill && map.containsKey(n)){
            return map.get(n);
        }
        String currNumber = map.get(hasValueTill);
        char[] charArray;
        int currIndex = 0;
        char currChar;
        //If the value does not exist in the map yet
        for(int i = hasValueTill+1; 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;
                map.put(i, currNumber);
                hasValueTill = i;
            }
        }
        return currNumber;
    }
    
}

Let’s address the runtime issue in another post soon!

Find more posts here.

Cheers & Chao!