My solution, one stack, O(n), using a symbol to make it simple.


  • 7
    B
    class Solution {
    public:
        bool isValid(string s) {
            stack<char> stk;
            stk.push('#');
            char top;
            for(int i(0); i < s.size(); i++)
            {
                top = stk.top();
                     if(top == '(' && s[i] == ')') stk.pop(); 
                else if(top == '[' && s[i] == ']') stk.pop(); 
                else if(top == '{' && s[i] == '}') stk.pop();
                else stk.push(s[i]);
            }
            top = stk.top();
            if(top == '#') return true;
            else           return false;
        }
    };
    

    Before scan the string, push a magic symbol '#' to the stack.

    If the string is valid, the top element of stack must be '#' after traversal.


  • 0
    G

    No need to use the '#' symbol, you can just go:

    return stk.size() == 0;


  • 0
    C

    You are right. But I think it has the advantage that no need to check stk is empty in the loop!


  • 0
    B

    Sure, that's the main reason why I do it~ : )


Log in to reply
 

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