Tuesday, May 7, 2013

Leetcode: Count and Say in C++



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


1 is read off as "one 1" or 11.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.

Solution:
string countAndSay(int n) {
        if(n==1)
        return "1";
        string current = "1";
        for(int i=2;i<=n;i++)
        {
            int pos = 1;
            int count =1;
            char pre = current[0];
            string tmp = "";
            while(pos<current.size())
            {
                if(current[pos]==pre)
                {
                    count++;
                }
                else
                {
                    stringstream ss;
                    ss << count;
                    tmp+=ss.str()+pre;
                    pre = current[pos];
                    count = 1;
                }
                pos++;
            }
            stringstream ss;
            ss << count;
            tmp+=ss.str()+pre;
            current = tmp;
        }
        return current;
    }

No comments:

Post a Comment