Count and Say

Tags: String, Easy

Question

Problem Statement

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 _n_th sequence.

Note: The sequence of integers will be represented as a string.

题解1 - 迭代

题目大意是找第 n 个数(字符串表示)，规则则是对于连续字符串，表示为重复次数+数本身。那么其中的核心过程则是根据上一个字符串求得下一个字符串，从 '1' 开始迭代 n - 1 次即可。

Python

  1. class Solution(object):
  2.     def countAndSay(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: str
  6.         """
  7.         if n <= 0:
  8.             return ''
  9.         seq = '1'
  10.         for _ in range(n - 1):
  11.             seq = re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1), seq)
  13.         return seq

Python

  1. class Solution(object):
  2.     def countAndSay(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: str
  6.         """
  7.         if n <= 0:
  8.             return ''
  10.         curr_seq = '1'
  11.         for j in range(n - 1):
  12.             curr_seq = self._get_next_seq(curr_seq)
  14.         return curr_seq
  16.     def _get_next_seq(self, seq):
  17.         next_seq = ''
  18.         cnt = 1
  19.         for i in range(len(seq)):
  20.             if i + 1 < len(seq) and seq[i] == seq[i + 1]:
  21.                 cnt += 1
  22.             else:
  23.                 next_seq += str(cnt)
  24.                 next_seq += seq[i]
  25.                 cnt = 1
  27.         return next_seq

C++

  1. class Solution {
  2. public:
  3.     string countAndSay(int n) {
  4.         if (n <= 0) return "";
  6.         string curr_seq = "1";
  7.         while (--n) {
  8.             curr_seq = getNextSeq(curr_seq);
  9.         }
  11.         return curr_seq;
  12.     }
  14. private:
  15.     string getNextSeq(string seq) {
  16.         string next_seq = "";
  17.         int cnt = 1;
  18.         for (int i = 0; i < seq.length(); i++) {
  19.             if (i + 1 < seq.length() && seq[i] == seq[i + 1]) {
  20.                 cnt++;
  21.             } else {
  22.                 next_seq.push_back('0' + cnt);
  23.                 next_seq.push_back(seq[i]);
  24.                 cnt = 1;
  25.             }
  26.         }
  28.         return next_seq;
  29.     }
  30. };

Java

  1. public class Solution {
  2.     public String countAndSay(int n) {
  3.         assert n > 0;
  4.         StringBuilder currSeq = new StringBuilder("1");
  5.         for (int i = 1; i < n; i++) {
  6.             currSeq = getNextSeq(currSeq);
  7.         }
  8.         return currSeq.toString();
  9.     }
  11.     private StringBuilder getNextSeq(StringBuilder seq) {
  12.         StringBuilder nextSeq = new StringBuilder();
  13.         int cnt = 1;
  14.         for (int i = 0; i < seq.length(); i++) {
  15.             if (i + 1 < seq.length() && seq.charAt(i) == seq.charAt(i + 1)) {
  16.                 cnt++;
  17.             } else {
  18.                 nextSeq.append(cnt).append(seq.charAt(i));
  19.                 cnt = 1;
  20.             }
  21.         }
  22.         return nextSeq;
  23.     }
  24. }

源码分析

字符串是动态生成的，Python 中 next_seq 使用了两次 append 而不是字符串直接拼接，实测性能有一定提升，C++ 中对整型使用了 push_back('0' + cnt), 容易证明 cnt 不会超过3，因为若出现1111，则逆向可得两个连续的1，而根据规则应为21，其他如2222推理方法类似。Java 中使用 StringBuilder 更为合适。除了通常方法外还可以使用正则表达式这一利器！

复杂度分析

略，与选用的数据结构有关。

题解2 - 递归

注意递归终止条件即可，核心过程差不多。

Python

  1. class Solution(object):
  2.     def countAndSay(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: str
  6.         """
  7.         if n <= 0:
  8.             return ''
  9.         if n == 1:
  10.             return '1'
  11.         seq = self.countAndSay(n - 1)
  12.         next_seq = ''
  13.         cnt = 1
  14.         for i in range(len(seq)):
  15.             if i + 1 < len(seq) and seq[i] == seq[i + 1]:
  16.                 cnt += 1
  17.             else:
  18.                 next_seq += str(cnt)
  19.                 next_seq += seq[i]
  20.                 cnt = 1
  22.         return next_seq

C++

  1. class Solution {
  2. public:
  3.     string countAndSay(int n) {
  4.         if (n <= 0) return "";
  5.         if (n == 1) return "1";
  7.         string seq = countAndSay(n - 1);
  8.         string next_seq = "";
  9.         int cnt = 1;
  10.         for (int i = 0; i < seq.length(); i++) {
  11.             if (i + 1 < seq.length() && seq[i] == seq[i + 1]) {
  12.                 cnt++;
  13.             } else {
  14.                 next_seq.push_back('0' + cnt);
  15.                 next_seq.push_back(seq[i]);
  16.                 cnt = 1;
  17.             }
  18.         }
  20.         return next_seq;
  21.     }
  22. };

Java

  1. public class Solution {
  2.     public String countAndSay(int n) {
  3.         assert n > 0;
  4.         if (n == 1) return "1";
  6.         String seq = countAndSay(n - 1);
  7.         StringBuilder nextSeq = new StringBuilder();
  8.         int cnt = 1;
  9.         for (int i = 0; i < seq.length(); i++) {
  10.             if (i + 1 < seq.length() && seq.charAt(i) == seq.charAt(i + 1)) {
  11.                 cnt++;
  12.             } else {
  13.                 nextSeq.append(cnt).append(seq.charAt(i));
  14.                 cnt = 1;
  15.             }
  16.         }
  18.         return nextSeq.toString();
  19.     }
  20. }

源码分析

判断相邻字符是否相同时需要判断索引是否越界。

复杂度分析

略，与选用的数据结构有关。

Reference