Tuesday, September 2, 2014

Look and say sequence puzzle in Java (1 11 21 1211 .....)

I recently came across with a question from one of my friends: The question is simple generate "nth" number in "Look and Say Sequence" given "1" as the initial string to start with. Here are more details about this sequence http://en.wikipedia.org/wiki/Look-and-say_sequence.

Look and Say Sequence is something like 1, 11, 21, 1211, 111221, 312211 and so on.. We need to find the nth number with in that sequence.

I thought it would be a very straight forward iterative approach and I could solve it in few minutes. However I faced few hiccups because of less paid attention.

Here is my solutions and I will explain the mistake I made in my first go.

private List<String> lookAndSayOf(int n) {
        List<String> results = new ArrayList<String>();
        results.add("1");
        for(int i=0; i<n; i++) {
            String token = results.get(i);
            char[] chars = token.toCharArray();
            String currentToken = "";
            int count = 0;
            char current = chars[0];
            for(int k=0; k<chars.length; k++) {
                if(current == chars[k]) {
                    count++;
                } else {
                    currentToken = currentToken+""+count+current;
                    count = 1;
                    current = chars[k];
                }
            }
            currentToken = currentToken+""+count+current;
            results.add(currentToken);
        }
        return results;
    }

Here two important things that we may miss in our first (I missed the second one)
- currentToken = currentToken+""+count+current; is required in both places (one is inside the loop and other is at the end of the loop. The inner one is to append the characters when there is a switch. The outer one is for the last switch. The work around to avoid the second statement (after the inner loop), add an extra space (extra character) at the end of the token something like String token = results.get(i)+" ";. This will make the loop run one extra time and we dont need the second statement.
- count = 1; We need to set the count back to 1 instead of zero.

No comments: