My solution, with one stack, in O(n) time, using a Map to make it more simple.


  • 0
    class Solution
    {
    public:
        bool isValid(std::string s)
        {
            std::map<char, char> symbols;
            symbols[')'] = '(';
            symbols[']'] = '[';
    		symbols['}'] = '{';
    		std::stack<char> stk;
    		for (std::string::size_type i = 0; i != s.size(); ++i)
    		{
    			if (symbols.find(s[i]) == symbols.end())
    			{
    				stk.push(s[i]);
    			}
    			else if (stk.empty())
    			{
    				return false;
    			}
    			else if (stk.top() == symbols[s[i]])
    			{
    				stk.pop();
    			}
    			else
    			{
    				return false;
    			}
    		}
    		if (stk.empty())
    		{
    			return true;
    		}
    		return false;
        }
    };

Log in to reply
 

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