Tuesday, September 9, 2014

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.
Understand the problem:
The problem is kind of tricky to understand. We can use some examples to illustrate it.
For input 1112, we "count-and-say", three 1s and one 2, so it is 3112
For input 112, two 1s and one 2, 2112
For input 1234, output is 11121314.

Actually this question is not very clear. The sequence starts from string "1", then the read of first string is the next string, which is 11, then 21, then 1211, ...., note that n start from 1, so i + 1 sequence is the read of sequence i, the nth sequence is the read of sequence n - 1. 


Code (Java):
public class Solution {
    public String countAndSay(int n) {
        if (n < 0) {
            return "";
        }
        
        String s = "1";
        
        for (int i = 0; i < n - 1; i++) {
            StringBuilder sb = new StringBuilder();
            int count = 1;
            
            int j = 0;
            while (j < s.length()) {
                while (j < s.length() - 1 && s.charAt(j) == s.charAt(j + 1)) {
                    count++;
                    j++;
                }
                sb.append(Integer.toString(count));
                sb.append(s.charAt(j));
                count = 1;
                j++;
            }
            
            s = sb.toString();
        }
        
        return s;
    }
}


1 comment:

  1. The above code does not work.
    The following works

    public String countAndSay(int n) {
    if (n < 0) {
    return "";
    }
    String s = Integer.toString(n);
    StringBuilder sb = new StringBuilder();
    int i = 0;
    while (i < s.length())
    {
    int count = 1;
    while (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1))
    {
    count++;
    i++;
    }
    sb.append(Integer.toString(count));
    sb.append(s.charAt(i));
    i++;
    }
    return sb.toString();
    }

    ReplyDelete