38. Count and Say

(Count and say in Laicode)

Given a sequence of number: 1, 11, 21, 1211, 111221, …

The rule of generating the number in the sequence is as follow:

1 is "one 1" so 11.

11 is "two 1s" so 21.

21 is "one 2 followed by one 1" so 1211.

Find the nth number in this sequence.

Assumptions:

• n starts from 1, the first number is "1", the second number is "11"

Analysis

My idea is using dp to store each number from 1 to n. The other solution did not use that many space, which is better in space complexity.

My solution

public String countAndSay(int n) {
  if (n == 1) {
      return "1";
  }
  if (n == 2) {
      return "11";
  }
  String[] m = new String[n + 1];
  m[1] = "1"; m[2] = "11";
  for (int i = 3; i <= n; ++i) {
      char[] last = m[i - 1].toCharArray();
    StringBuilder sb = new StringBuilder();
    int j = 0;
    while (j < last.length) {
        int k = j + 1;
      while (k < last.length) {
          if (last[k] == last[j]) {
            k++;
        } else {
            break;
        }
      }
      if (k - j == 1) {
          sb.append(1); sb.append(last[j]);
      } else {
          sb.append(k - j); sb.append(last[j]);
      }
      j = k;
    }
    m[i] = sb.toString();
  }
  return m[n];
}

Better Solution:

public String countAndSay(int n) {
    String s = "1";
    while (n-- > 1) { 
        StringBuilder next = new StringBuilder(); 
        for (int i = 1, cnt = 1; i <= s.length(); i++, cnt++) {
            if (i == s.length() || s.charAt(i) != s.charAt(i - 1)) {
                next.append(cnt).append(s.charAt(i - 1));
                cnt = 0;
            }
        }
        s = next.toString();
    }
    return s;
}