C++ solution, runtime O(n), space O(n)


  • 12
    J

    Please see the comments in the code.
    The solution is quite straight-forward. We generate k-th string, and from k-th string we generate k+1-th string, until we generate n-th string.
    We use string-helper to save temporary result,
    I'm sure there is a way for in-place solution also.

    class Solution {
    public:
    
        std::string countAndSay(int n) {
        
        	if (0 == n) return "";  
        	if (1 == n) return "1";
        	
        	std::string res="1";
        	std::string s;
        
        	for (int i = 1; i < n; i++){    // run from starting to generate second string
        
        		int len = res.size();
                
                //cheack all digits in the string
        		for (int j = 0; j < len; j++){  
        		    
        		    int count=1; // we have at least 1 occourence of each digit
        
                    // get the number of times same digit occurred (be carefull with the end of the string)
    				while ((j + 1 < len) && (res[j] == res[j + 1])){
    					count++;    
    					j++;        // we need to keep increasing the index inside of the string
    				}
                    
                    // add to new string "count"+"digit itself"
        			s += std::to_string(count) + res[j];
        		}
        
                // save temporary result
        		res = s;
        		
        		// clean our string-helper
        		s.clear();
        
        	}
        
        	return res;
        }
    };

  • 0
    N

    concise and beautiful


  • 0
    J

    Thank you, I was just thinking about in-place solution...what if we:

    1. double the size of the k-th string in advance
    2. generate k+1-th string starting to traverse the k-th string backward (in-place)
    3. adjusting the size.

  • 0
    Y
        string countAndSay(int n) {
    	if (n==0)
    		return "";
    	if (n==1)
    		return "1";
    
    	string res = "";
    	string pre = countAndSay(n-1);
    	int len = pre.length();
    
    	for(int i = 0;i< len ; i++ ){
    		int count = 1;
    		while (i+1<len && pre[i]==pre[i+1])
    		{
    			i++;
    			count ++;
    		}
    		
    	//res += std::to_string(count);
    	char count_s [20];
    	sprintf(count_s,"%d",count);
    
    	res += count_s;
    	res += res[i];
    	}
    	return res; 
    }
    

    what's wrong in this code ,if i want to use Recursion?


  • 7
    M

    The runtime is not O(n), you perform n steps and on each step you iterate over the length of the current string at that step which is also increasing per step. This is order O(n*m) where m is the length of the string at step n.


  • 1
    J

    I agree with you, and I think we can say Runtime is O(n*k).


  • 0
    J

    Thinking a little bit more, we can calculate total runtime as sum of geometric progression 1*(2^k - 1)/(2-1) = 2^k - 1, which is O(2^k)
    If you check it, the length almost doubles every step.
    I believe that is why total number of test cases is not big too, just 18.


  • 0
    J

    i+i in pre[i+1] will be out of bound


  • 1
    S

    I used a helper function to make the code easy to read. A slow pointer and a fast pointer are used to track the length of continuous digit. Use 'count++' is fine too.

    string helper(string &r)
    {
        // i is fast pointer, j is slow pointer
        string rst = "";
        int j = 0;
        for (int i = 0; i < r.size(); i++)
        {
            j = i;
            while(i + 1 < r.size() && r[i] == r[i + 1])
            {
                i++;
            }
            rst += (i - j + 1) + '0';
            rst += r[j];            
        }
        return rst;
    }
    string countAndSay(int n) {
        string r = "1";
        string prev = r;
        
        for (int i = 2; i <= n; i++)
        {
            prev = r;
            r = helper(prev);
        }
        return r;
    }

  • 0
    Z
    This post is deleted!

  • 0
    Z

    I think Runtime is at least O(N^2). To generate k+1th sequence from kth sequence. You have to iterate kth sequence whose length is at least k. Because the length of each sequence is guaranteed to increase, but not necessarily doubled as in JackBauer's answer.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.