Question

Formatted question description: https://leetcode.ca/all/38.html

38	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.

Algorithm

The algorithm is very simple, that is, for the previous number, find the number of the same element, and store the number and the element in the new string.

Code

Java

• Java
• C++
• Python

• 
  public class Count_and_Say {
  
      public String countAndSay(int n) {
  
          // @note: possibly overflow is n is large enough
          if(n <= 0) {
              return "";
          }
  
          String result = "1";
  
          while(n > 1) {
              char prev = result.charAt(0);
              int count = 1;
              String say = "";
  
              int i = 1;
              for(; i < result.length(); i++) {
                  char current = result.charAt(i);
  
                  if (current == prev) {
                      count++;
                  } else {
                      say += count + "" + prev;
  
                      // reset count
                      count = 1;
                      prev = current;
                  }
  
              }
  
              // check for last digit say
              say += count + "" + prev;
  
              result = say;
              n--;
          }
  
          // @note: string to int api: Integer.valueOf(result)
          return result;
      }
  
  
  	/*
  	 * @note:
  	 *
  	 * 		这道题非常的tricky
  	 * 		String的 += "x"的操作是比较expensive的，StringBuilder比较省
  	 *
  	 * 	StringBuilder的编译效率更高
  	 * 	ref:
  	 * 		http://stackoverflow.com/questions/14927630/java-string-concat-vs-stringbuilder-optimised-so-what-should-i-do
  	 *
  	 * 		注意坑，就是每次for loop完了之后，还有最后的一个count和say要加到结果里
  	 */
  	public class Solution {
  
  	    StringBuilder sb = new StringBuilder();
  
  	    // my thought, use iteration
  	    public String countAndSay(int n) {
  
  	        sb.append("1");
  
  	        StringBuilder newsb = new StringBuilder();
  
  	        for (int i = 1; i < n; i++) {
  
  	            // go through this string
  	            char previous = sb.charAt(0);
  	            int count = 1;
  
  	            // // add checking first input "1"...
  	            // if (sb.length() == 1) {
  	            //     sb.append(count);
  	            //     sb.append(previous);
  	            // }
  
  
  	            for (int j = 1; j < sb.length(); j++) {
  
  	                char curr = sb.charAt(j);
  
  	                if (curr == previous) {
  	                    count++;
  	                }
  	                // else if (curr != previous && j != sb.length() - 1) {
  	                else {
  	                    // sayIt(count, previous);
  	                    newsb.append(count);
  	                    newsb.append(previous);
  
  	                    // update
  	                    previous = curr;
  	                    count = 1;
  	                }
  	                // else {
  	                //     // sayIt(count, previous);
  	                //     newsb.append(count);
  	                //     newsb.append(previous);
  	                // }
  	            }
  
  	            // append the last one
  	            newsb.append(count);
  	            newsb.append(previous);
  
  	            // update sb
  	            sb = new StringBuilder(newsb);
  	            // @note: sb has NO clear()
  	            // newsb.clear();
  	            newsb = new StringBuilder();
  	        }
  
  	        return sb.toString();
  	    }
  	}
  
  }
  

• // OJ: https://leetcode.com/problems/count-and-say/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      string countAndSay(int n) {
          if (n == 1) return "1";
          string s = countAndSay(n - 1), ans;
          for (int i = 0, N = s.size(); i < N; ++i) {
              char d = s[i];
              int cnt = 1;
              while (i + 1 < N && s[i + 1] == s[i]) ++i, ++cnt;
              ans += to_string(cnt) + d;
          }
          return ans;
      }
  };
  

• class Solution(object):
    def countAndSay(self, n):
      """
      :type n: int
      :rtype: str
      """
      ans = "1"
      n -= 1
      while n > 0:
        res = ""
        pre = ans[0]
        count = 1
        for i in range(1, len(ans)):
          if pre == ans[i]:
            count += 1
          else:
            res += str(count) + pre
            pre = ans[i]
            count = 1
        res += str(count) + pre
        ans = res
        n -= 1
      return ans
  
  

All Problems

All Solutions