C++ Solution Decode String using stack


  • 0
    R

    class Solution {
    public:
    string repeat(string s, int count)
    {
    if (count == 0) return "";
    if (count == 1) return s;
    string tmp = repeat(s, count / 2);
    tmp += tmp;
    if (count % 2 != 0)
    tmp += s;
    return tmp;
    }

    string decodeString(string s)
    {
    	int sLen = s.size();
    	string output;
    	if (sLen == 0)
    	{
    		return output;
    	}
    
    	stack<int> cntStk;
    	stack<string> strStk;
    
    	size_t pos = 0;
    	while (pos < sLen)
    	{
    		if (isdigit(s[pos]))
    		{
    			size_t savedPos;
    			
    			savedPos = pos;
    			pos = s.find_first_of("[", savedPos);
    			size_t cnt = atoi(s.substr(savedPos, pos - savedPos).c_str());
    
    			savedPos = pos + 1;
    			pos = s.find_first_of("]0123456789", savedPos);
    			string str = s.substr(savedPos, pos - savedPos);
    
    			cntStk.push(cnt);
    			strStk.push(str);
    		}
    		else if (isalpha(s[pos]))
    		{
    			size_t savedPos;				
    			savedPos = pos;
    			pos = s.find_first_of("]0123456789", savedPos);
    			string str = s.substr(savedPos, pos - savedPos);
    			output += str;
    		}
    		else if (s[pos] == ']')
    		{
    			++pos;
    
    			string str = strStk.top();
    			int cnt = cntStk.top();
    			strStk.pop();
    			cntStk.pop();
    
    			str = repeat(str, cnt);
    
    			if (strStk.empty())
    			{
    				output += str;
    			}
    			else
    			{
    				strStk.top() += str;
    			}
    		}
    	}
    	return output;
    }
    

    };


Log in to reply
 

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