38. Count and Say

發表於 | 分類於

problem

solution

option 1 iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for(int i=1;i<n;++i){
            string path ;
            int count = 1, val = ret[0];
            for(int j=1;j<ret.size() ; ++j){
                if(ret[j] == val) count++;
                else{
                    path+=to_string(count);
                    path+=val;
                    count = 1;
                    val = ret[j];
                }
            }
            if(count > 0) {path+=to_string(count);path+=val;}
            ret = path;
        }
        return ret;
    }
};

option 2 recursive

1

analysis

  • time complexity O(nlogn)
  • space complexity O(nm)