Question

38. Count and Say

中文文档

Description

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you "say" a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return _the _nth_ term of the count-and-say sequence_.

 

Example 1:

Input: n = 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

 

Constraints:

• 1 <= n <= 30

Solutions

Solution 1: Simulation

The task requires outputting the appearance sequence of the $n$-th item, where the $n$-th item is the description of the $n-1$-th item in the sequence. Therefore, we iterate $n-1$ times. In each iteration, we use fast and slow pointers, denoted as j and i respectively, to record the current character's position and the position of the next character that is not equal to the current character. We then update the sequence of the previous item to be $j-i$ occurrences of the current character.

Time Complexity:

1. The outer loop runs n - 1 times, iterating to generate the "Count and Say" sequence up to the nth term.
2. The inner while loop iterates through each character in the current string s and counts the consecutive occurrences of the same character.
3. The inner while loop runs in $O(m)$ time, where m is the length of the current string s.

Overall, the time complexity is $O(n \times m)$, where n is the input parameter representing the term to generate, and m is the maximum length of the string in the sequence.

Space Complexity: $O(m)$.

class Solution:
  def countAndSay(self, n: int) -> str:
    s = '1'
    for _ in range(n - 1):
      i = 0
      t = []
      while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
          j += 1
        t.append(str(j - i))
        t.append(str(s[i]))
        i = j
      s = ''.join(t)
    return s

class Solution {
  public String countAndSay(int n) {
    String s = "1";
    while (--n > 0) {
      StringBuilder t = new StringBuilder();
      for (int i = 0; i < s.length();) {
        int j = i;
        while (j < s.length() && s.charAt(j) == s.charAt(i)) {
          ++j;
        }
        t.append((j - i) + "");
        t.append(s.charAt(i));
        i = j;
      }
      s = t.toString();
    }
    return s;
  }
}

class Solution {
public:
  string countAndSay(int n) {
    string s = "1";
    while (--n) {
      string t = "";
      for (int i = 0; i < s.size();) {
        int j = i;
        while (j < s.size() && s[j] == s[i]) ++j;
        t += to_string(j - i);
        t += s[i];
        i = j;
      }
      s = t;
    }
    return s;
  }
};

func countAndSay(n int) string {
  s := "1"
  for k := 0; k < n-1; k++ {
    t := &strings.Builder{}
    i := 0
    for i < len(s) {
      j := i
      for j < len(s) && s[j] == s[i] {
        j++
      }
      t.WriteString(strconv.Itoa(j - i))
      t.WriteByte(s[i])
      i = j
    }
    s = t.String()
  }
  return s
}

function countAndSay(n: number): string {
  let s = '1';
  for (let i = 1; i < n; i++) {
    let t = '';
    let cur = s[0];
    let count = 1;
    for (let j = 1; j < s.length; j++) {
      if (s[j] !== cur) {
        t += `${count}${cur}`;
        cur = s[j];
        count = 0;
      }
      count++;
    }
    t += `${count}${cur}`;
    s = t;
  }
  return s;
}

use std::iter::once;

impl Solution {
  pub fn count_and_say(n: i32) -> String {
    (1..n)
      .fold(vec![1], |curr, _| {
        let mut next = vec![];
        let mut slow = 0;
        for fast in 0..=curr.len() {
          if fast == curr.len() || curr[slow] != curr[fast] {
            next.extend(once((fast - slow) as u8).chain(once(curr[slow])));
            slow = fast;
          }
        }
        next
      })
      .into_iter()
      .map(|digit| (digit + b'0') as char)
      .collect()
  }
}

const countAndSay = function (n) {
  let s = '1';

  for (let i = 2; i <= n; i++) {
    let count = 1,
      str = '',
      len = s.length;

    for (let j = 0; j < len; j++) {
      if (j < len - 1 && s[j] === s[j + 1]) {
        count++;
      } else {
        str += `${count}${s[j]}`;
        count = 1;
      }
    }
    s = str;
  }
  return s;
};

using System.Text;
public class Solution {
  public string CountAndSay(int n) {
    var s = "1";
    while (n > 1)
    {
      var sb = new StringBuilder();
      var lastChar = '1';
      var count = 0;
      foreach (var ch in s)
      {
        if (count > 0 && lastChar == ch)
        {
          ++count;
        }
        else
        {
          if (count > 0)
          {
            sb.Append(count);
            sb.Append(lastChar);
          }
          lastChar = ch;
          count = 1;
        }
      }
      if (count > 0)
      {
        sb.Append(count);
        sb.Append(lastChar);
      }
      s = sb.ToString();
      --n;
    }
    return s;
  }
}