Skip to content

LeetCode: 38-Count and Say 解題紀錄

Last Updated on 2021-02-21 by Clay

題目

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 groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
Given a positive integer n, return the nth term of the count-and-say sequence.

Example:

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

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"

這個題目我反覆看了好幾遍，最後才總算弄明白題目的意思：題目給定要『展開的次數 n』，在 n = 1 時，最基本的案例為 "1"，這是一切的基礎。

n = 2 時，因為 "1" 只有 1 個，所以為我們稱其為 one 1，也就是 "11"。

n = 3 時，因為 "11" 有 2 個 1，所以稱其為 two 1，也就是 "21"。

n = 4 時，因為 "2" 以及 "1" 都各自只有 1 個，所以稱其為 one 2 one 1，也就是 "1211"。

以此類推，一直展開我們的字串。

解題思路

我的想法非常單純，使用陣列紀錄重複的字元、以及字元重複的次數，然後將其儲存成新的字串。接下來，就是看題目要我們迭代幾次，我們就展開多少次字串。


C++ 程式碼

class Solution {
public:
    string countAndSay(int n) {
        // Init
        int times = 1;
        string s = "1";
        
        // Unfold
        while (times < n) {
            ++times;
            char c = '0';
            vector<char> vc;
            vector<int> vcn;
            
            // Count the numbers of repeat characters
            for (int i=0; i<s.size(); ++i) {
                if (s[i] != c) {
                    c = s[i];
                    vc.push_back(s[i]);
                    vcn.push_back(1);
                }
                else {
                    ++vcn[vc.size()-1];
                }
            }
            
            // Clear the current string
            s.clear();
            
            // Create the new string
            for (int i=0; i<vc.size(); ++i) {
                s += to_string(vcn[i]);
                s += vc[i];
            }
        }
        
        return s;
    }
};


Python 程式碼

class Solution:
    def countAndSay(self, n: int) -> str:
        # Init
        times = 1
        s = "1"
        
        # Unfold
        while times < n:
            times += 1
            c = "0"
            vc = []
            vcn = []
            
            # Count the numbers of repeat characters
            for w in s:
                if w != c:
                    c = w
                    vc.append(w)
                    vcn.append(1)
                else:
                    vcn[-1] += 1
            
            # Clear the current string
            s = ""
            
            # Create the new string
            for i in range(len(vc)):
                s += str(vcn[i]) + vc[i]
            
        return s;


References

Tags:

Leave a Reply