20. Valid Parentheses

problem description

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

algorithm thought

括号匹配问题在上数据结构课上也是会讲的。没学过数据结构之前可能很难相出用栈来做这题，学完之后就很显然了。其实栈的用处很大，在之后很多地方也会用到。线性处理一组数据的时候，如果需要满足某些条件，可以考虑一下能否用栈解决。这题就是线性处理一个字符串，并且需要满足一些条件。最近的一个括会肯定要和最近出现的一个括首匹配。用一个栈保存最近出现的括首即可

code

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

algorithm analysis

一个循环线性处理一个字符串，时间复杂度O(n)。