Count and Say

LeetCode #38

Description:

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...

Example:

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.

Idea:

不要用stl的函数，自己写函数findNotEqual。

Code:

class Solution {
public:
    string countAndSay(int n) {
        string sequence="1";

        while(n!=1){
            sequence = getNext(sequence);
            n--;
        }
        return sequence;
    }
    int findNotEqual(const string & s, int i){ 
    // Find the next position where s[j]!=s[i]
        int j=i+1;
        while(j!=s.size()&&s[j]==s[i]){
            j++;
        }
        return j;
    }
    string getNext(const string& s){
        string result;
        for(int i=0; i<s.size();){
            int j=findNotEqual(s, i);
            result += to_string(j-i)+s[i];
            i=j;
        }

        return result;
    }
};