38. Посчитай и скажи (Count and Say)

Задание.

Последовательность “Посчитай и скажи” – это последовательность строк цифр, определяемая рекурсивной формулой:

• countAndSay(1) = "1"

• countAndSay(n) – это способ, которым вы бы “произнесли” строку цифр из countAndSay(n-1), которая затем преобразуется в другую строку цифр.

Чтобы определить, как вы “произносите” цифровую строку, разделите ее на минимальное количество подстрок таким образом, чтобы каждая подстрока содержала ровно одну уникальную цифру. Затем для каждой подстроки произнесите количество цифр, затем произнесите цифру. Наконец, объедините каждую указанную цифру.

Например, высказывание и преобразование для цифровой строки “3322251” выглядит так:

Получив положительное целое число n, верните n-й член последовательности “посчитай и скажи”.

Пример 1.

Входные данные: n = 1

Результат: “1”

Пояснение: Это базовый вариант.

Пример 2.

Входные данные: n = 4

Результат: “1211”

Пояснение:

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"

Решение.

class Solution {
public:
    string countAndSay(int n) {
        if(n == 1) return "1";
        if(n == 2) return "11";
        int i, j, count, len;
        string s, prev = "11";
        for(i = 3; i <= n; i++) {
            s = "";
            count = 1;
            len = prev.length();
            for(j = 1; j < len; j++) {
                if(prev[j] == prev[j-1]) {
                    count++;
                } else {
                    s += to_string(count) + prev[j-1];
                    count = 1;
                }
            }
            s += to_string(count) + prev[j-1];
            prev = s;
        }
        return s;
    }
};