Sunday, September 10, 2017

38. Count and Say

https://leetcode.com/problems/count-and-say/description/
Solution 1. (0 ms)
    string countAndSay(int n) {
        if(n==1) return "1";
        string s = countAndSay(n-1);
        string res = "";
        int cnt = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] != s[i-1]) {
                res.push_back('0' + cnt);
                res.push_back(s[i-1]);
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        res.push_back('0' + cnt);
        res.push_back(s.back());
        return res;
    }
Solution 1.1  (3 ms)
res += to_string(cnt) + s[i-1]; is slower than res.push_back('0' + cnt); res.push_back(s[i-1]);
    string countAndSay(int n) {
        if(n==1) return "1";
        string s = countAndSay(n-1);
        string res = "";
        int cnt = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] != s[i-1]) {
                res += to_string(cnt) + s[i-1];
                cnt = 1;
            }
            else {
                cnt++;
            }
        }
        res += to_string(cnt) + s.back();
        return res;
    }

No comments:

Post a Comment