Leetcode 38 Solution

This article provides solution to leetcode question 38 (count-and-say)
Categories:
Tags:
Access this page by simply typing in "lcs 38" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/count-and-say

Thinking Process

Nothing fancy about this question, just simulate the calculate of countAndSay(n) from countAndSay(n - 1). And then do it n times.

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(2^n)

Solution

class Solution {
public:
    string translate(const string& s)
    {
        int last_cnt = 1;
        char last_ch = s[0];
        string res;

        for (int i = 1; i < s.size(); i++)
        {
            if (last_ch == s[i])
                last_cnt++;
            else
            {
                res += to_string(last_cnt) + last_ch;
                last_cnt = 1;
                last_ch = s[i];
            }
        }

        if (last_cnt)
            res += to_string(last_cnt) + last_ch;
        return res;
    }

    string countAndSay(int n) {
        if (n == 0)
            return "";

        string s = "1";

        for (int i = 2; i <= n; i++)
            s = translate(s);

        return s;
    }
};