题目

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

分析

可以用栈来实现。碰到左边的括号就入栈，碰到右边的就出栈，并判断是否匹配。

实现

class Solution {
public:
    bool isValid(string s) {
        stack<int> Stack;
        map<char, char> Map={{'(',')'}, {'{','}'}, {'[',']'}};
        for(auto ch: s){
            if(ch=='('||ch=='{'||ch=='[')
                Stack.push(ch);
            else{
                if((!Stack.empty())&&Map[Stack.top()]==ch)
                    Stack.pop();
                else
                    return false;
            }
        }
        if(Stack.empty())
            return true;
        else
            return false;
    }
};

思考

一开始忘记了碰到右括号时要先判断栈是否非空，还是要细心呀。