博客

20. 有效的括号



20. Valid Parentheses

题目：

给定一个只包括

'('

，

')'

，

'{'

，

'}'

，

'['

，

']'

的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”

输出: true

示例 2:

输入: “()[]{}”

输出: true

示例 3:

输入: “(]”

输出: false

题解:

主要使用栈。遇到左括号

'('

,

'['

,

'{'

时，直接入栈，遇到右括号

‘)’

,

']'

,

'}'

时，则与栈顶元素比较，如果是匹配的，则直接将栈顶元素出栈，如果栈为空或者不匹配，则直接返回

False

。括号字符串遍历结束后，还需要检查栈是否为空，为空才表示是一个合法的括号组合。

技巧：

使用

map

，以右括号为

key

，左括号为

value

，可以减少代码量。

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char, char> map;//给括号建立map
        map[')'] = '(';
        map['}'] = '{';
        map[']'] = '[';
        for(auto c : s){
            switch(c){
                case '('://左括号直接入栈
                case '[':
                case '{':
                    st.push(c);
                    break;
                case ')':
                case ']':
                case '}':
                    if(st.empty() || st.top() != map[c]){//栈为空或者与栈顶不匹配，返回false
                        return false;
                    }
                    st.pop();
                    break;
            }
        }
        return st.empty();//栈为空则是合法的
    }
};

Java

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<Character>();
        HashMap<Character, Character> map = new HashMap<Character, Character>(){{
            put( ')', '(');
            put( ']', '[');
            put( '}', '{');
        }};
        char chrs[] = s.toCharArray();
        for(Character c : chrs) {
            switch(c) {
                case '('://处理左括号
                case '[':
                case '{':
                    st.push(c);
                    break;
                case ')'://右括号
                case ']':
                case '}':
                    if(st.empty() || st.pop() != map.get(c)) {//栈为空或者栈顶元素不匹配，返回false
                        return false;
                    }
                    break;
            }
        }
        return st.empty();//栈为空则合法
    }
}

Python

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        st = []
        dic = {')':'(', '}':'{', ']':'['} # 括号的map
        for c in s:
            if c == '(' or c == '[' or c == '{':# 左括号
                st.append(c)
            elif c == ']' or c == ')' or c == '}':# 右括号
                if len(st) == 0 or st.pop() != dic[c]: # 栈为空或者栈顶不匹配，返回false
                    return False
        return len(st) == 0