C++ iterative solution with explanation, easy to understand.


  • 5
    K

    Renewed Solution

    The key point here is to find the maximum consecutive identical numbers, which means, for example:

    Say there is a array like this [1, 1, 2, 3, 4, 4, 5, 5, 5], we will need to divide the array into different segments like this, [1, 1], [2], [3], [4, 4], [5, 5, 5]. Only in this way, can we count the occurrence of each consecutive segments and convert them into "21 12 13 24 35".

    The description of the problem is misleading and I struggled for a while, after some searching I found the right explanation. The number n has nothing to do with the algorithm directly, but but only control the number of iteration.

    The problem can be solved by using iterative algorithm.

    Code

    string countAndSay(int n)
    {
        string curr_str;
    
    	// The initial case, when n = 1
    	curr_str += '1';
    
    	// The iterative case, when n > 1
    	for (int i = 0; i < n - 1; i++)
    	{
    		string buffer;
    
    		// Handle the current string
    		int index = 0;
    		for (int index = 0; index < curr_str.size(); ++index)
    		{
    			// Count the occurance of each digit
    			int cnt = 1; // At least one occurance
    			
    			while (index + 1 < curr_str.size() and curr_str[index + 1] == curr_str[index]) 
    			{
    				index++;
    				cnt++;
    			}
    
    			buffer.push_back(cnt + '0');
    			buffer.push_back(curr_str[index]);
    		}
    
    		// Update the current string
    		curr_str = buffer;
    	}
    
    	return curr_str;
    }

  • 0
    F

    "while (currstr[j] == currstr[j + 1] && j < currstr.size())"
    Is it safe when j=currstr.size()-1? What's the value of currstr[j+1] in this case?


  • 0
    K

    Thank you for your valuable comment. I did some searching and found some explanation here :
    http://en.cppreference.com/w/cpp/string/basic_string/operator_at

    There's a flaw but I think it's not that severe here. Anyway, we can change it to j + 1< curr_str.size() && curr_str[j] == curr_str[j + 1]


Log in to reply
 

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