Solution to LeetCode Problems: Count and Say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.
Note: The sequence of integers will be represented as a string.

Thoughts:
Scan the string while maintaining a "state" that counts the numbers. Save previous results for accelerating the next string generation.


Solution:

1. class Solution {  
2. public:  
3.     // save previous history for accelerated calculation  
4.     vector<string> history;  
5.       
6.     Solution()  
7.     {  
8.         history.emplace_back(string("1"));  
9.     }  
10.       
11.     string generate_seq(const string& in)  
12.     {  
13.         string generated;  
14.         char scratch[64];  
15.         char current = in[0];  
16.         int count = 0;  
17.           
18.         auto commit = [&]()  
19.         {  
20.             sprintf(scratch, "%d%c", count, current);  
21.             generated += scratch;  
22.         };  
23.           
24.         for(auto ch : in)  
25.             if (ch != current)  
26.             {  
27.                 // we met another character  
28.                 commit();  
29.   
30.                 count = 1;  
31.                 current = ch;  
32.             }  
33.             else  
34.                 ++count;  
35.           
36.         commit();   // commit the last continuous char accumulation  
37.         return generated;  
38.     }  
39.       
40.     string countAndSay(int n)   
41.     {  
42.         while(n-1 >= history.size())  
43.             // exploit the r-value reference  
44.             history.emplace_back(generate_seq(history.back()));  
45.               
46.         return history[n-1];  
47.     }  
48. };