38. Count and Say

public class Solution {
    public string CountAndSay(int n) {
        string s = "1";
        for (int i = 0; i < n - 1; i++) {
            StringBuilder current = new StringBuilder();
            for (int j = 0; j < s.Length; j++) {
                int count = 1;
                while (j < s.Length - 1 && s[j] == s[j + 1]) {
                    j++;
                    count++;
                }
                current.Append(count);
                current.Append(s[j]);
            }
            s = current.ToString();
        }
        return s;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string CountAndSay(int n) {
        string s = "1";
        for (int i = 0; i < n - 1; i++) {
            StringBuilder current = new StringBuilder();
            for (int j = 0; j < s.size(); j++) {
                int count = 1;
                while (j < s.size() - 1 && s[j] == s[j + 1]) {
                    j++;
                    count++;
                }
                current.Append(count);
                current.Append(s[j]);
            }
            s = current.ToString();
        }
        return s;
    }
}

import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public String countAndSay(int n) {
        String currentString = "1";
        Pattern pattern = Pattern.compile("(.)\\1*");
        for (int i = 1; i < n; ++i) {
            Matcher m = pattern.matcher(currentString);
            StringBuffer nextString = new StringBuffer();
            while (m.find()) {
                nextString.append(
                    m.group().length() + String.valueOf(m.group().charAt(0))
                );
            }
            currentString = nextString.toString();
        }
        return currentString;
    }
}

class Solution {
  countAndSay(n) {
    if (n === 1) {
      return "1"; // Base case
    }

    let ans = "";
    let temp = "1";

    for (let i = 2; i <= n; i++) {
      let cnt = 0;
      let prev = temp[0];

      for (let j = 0; j < temp.length; j++) {
        const char = temp[j];

        if (prev === char) {
          cnt++; // brute force
        } else {
          ans += cnt.toString(); // adding count to the end
          ans += temp[j - 1];
          prev = char;
          cnt = 1;
        }
      }

      ans += cnt.toString();
      ans += temp[temp.length - 1];
      temp = ans; // assigning ans to temp and making ans = ""
      ans = ""; // so that we can iterate over temp again!
    }

    return temp;
  }
}

class Solution:
    def countAndSay(self, n: int) -> str:
        s = "1"
        for _ in range(n - 1):
            s = re.sub(
                r"(.)\1*", lambda m: str(len(m.group(0))) + m.group(1), s
            )
        return s

func countAndSay(n int) string {
    s := "1"
    for i := 2; i <= n; i++ {
        t := ""
        count := 1
        for j := 1; j < len(s); j++ {
            if s[j] == s[j-1] {
                count++
            } else {
                t += strconv.Itoa(count) + string(s[j-1])
                count = 1
            }
        }
        t += strconv.Itoa(count) + string(s[len(s)-1])
        s = t
    }
    return s
}

Algorithm

1️⃣

Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222".

Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает.

2️⃣

Мы можем разбить это регулярное выражение на три части:

(.): оно определяет группу, содержащую один символ, который может быть чем угодно.

3️⃣

*: этот квалификатор, следующий за ссылкой на группу \1, указывает, что мы хотели бы видеть повторение группы ноль или более раз.

Таким образом, шаблон соответствует строкам, которые состоят из некоторого символа, а затем ноль или более повторений этого символа после его первого появления. Это то, что нам нужно.

Мы находим все совпадения с регулярным выражением, а затем конкатенируем результаты.

😎