Written by DK-Lite
on December 07, 2019

[LeetCode .38] Count and Say

Count and Say.

Problem

n = 1, “1”로 시작하여 주어진 N으로 문자열을 출력
규칙은 N-1번쨰의 문자열을 뒤에서 부터 같은 숫자가 몇개 있는지를
문자열로 소리나는대로 적으면된다.

Solution

Recurrent

n = 1 일때 “1”
countAndSay 메소드는 n-1의 string을 받아 뒤에서 부터 읽어들여 아래의 규칙으로 처리
1. N-1번째의 문자열을 뒤에서 읽어오며 같은 문자열을 카운팅 한후 vector에 순서대로 Push
2. vector reverse
3. result string을 만들어서 출력

Code

class Solution {
public:
    string dp[31] = {"",};
    string countAndSay(int n) {

        if (n == 1) return "1";

        string say = countAndSay(n - 1);
        vector<string> tmp;
        int idx = say.size() - 1;
        while (idx >= 0) {
            tmp.push_back(to_string(say[idx] - '0'));
            int cnt = 1;
            while (idx > 0 && say[idx] == say[idx - 1]) {
                cnt++, idx--;
            }
            tmp.push_back(to_string(cnt));
            idx--;
        }
        reverse(tmp.begin(), tmp.end());
        string result = "";

        for (string str : tmp) result += str;

        return result;
    }
};

← → Top