Share my solution. 0ms. And have one more question.


  • 0
    class Solution {
    public:
    string countAndSay(int n) {
        string s="1";
        for(int i=1; i<n; ++i){
            string t;
            for(int j=0; j<s.length();){
                char c=s[j];
                int cnt=0;
                while(j<s.length() && c==s[j]){
                    ++j; ++cnt;
                }
                t.push_back('0'+cnt);
                t.push_back(c);
            }
            swap(s, t);
        }
        return s;
    }};
    

    My question is, it looks that the string sequence would only have '1', '2', '3'. Can we prove this?


  • 0
    J

    Say we have a sequence Seq, Seq doesn't contain any 4, and Seq don't have 4 consecutive identical number yet (maybe there will be, but not yet).

    Say there is a sub sequence like this: (a)(b)(c) --- (a) means 'aaa', 'aa', 'a'. same for the b and c.

    With constraint: a!=b b!=c
    countAndSay((a)(b)(c)) would be 'manbpc' (m = 1, 2, 3 ; n = 1, 2, 3; p=1, 2, 3), when put the constraint on the output 'manbpc' a!=b&&b!=c (but still n==b b==p is possible), it means that there won't be a 4 consecutive identical number in the sequence. thus there won't be a 4 or 5 or larger number in the sequence.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.