0020. 有效的括号 [Easy] [Valid Parentheses].md

20. Valid Parentheses

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

---

题目：判断字符串表达式是否为合法的括弧对。

思路：利用栈。如果遇到了右括弧，则弹出栈顶元素，判断是否匹配；如果遇到的为左括弧，则压入栈中；最后判断栈中元素是否为空。

工程代码下载

class Solution {
public:
    bool isValid(string s) {
        map<char, char> bracket{ {')', '('}, {'}', '{'}, {']', '['} };
        stack<char> st;
        for(auto c : s){
            if(bracket.find(c) != bracket.end()){
                if(st.empty())
                    return false;

                char top_element = st.top();
                st.pop();

                if(top_element != bracket[c])
                    return false;
            }
            else
                st.push(c);
        }
        return st.empty();
    }
};

参考Approach 1: Stacks.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """

        # The stack to keep track of opening brackets.
        stack = []

        # Hash map for keeping track of mappings. This keeps the code very clean.
        # Also makes adding more types of parenthesis easier
        mapping = {")": "(", "}": "{", "]": "["}

        # For every bracket in the expression.
        for char in s:

            # If the character is an closing bracket
            if char in mapping:

                # Pop the topmost element from the stack, if it is non empty
                # Otherwise assign a dummy value of '#' to the top_element variable
                top_element = stack.pop() if stack else '#'

                # The mapping for the opening bracket in our hash and the top
                # element of the stack don't match, return False
                if mapping[char] != top_element:
                    return False
            else:
                # We have an opening bracket, simply push it onto the stack.
                stack.append(char)

        # In the end, if the stack is empty, then we have a valid expression.
        # The stack won't be empty for cases like ((()
        return not stack