leetcode 20题解【C++/Java/Python】-白红宇

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

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

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

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

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

题解:

主要使用栈。遇到左括号'(', '[', '{'时，直接入栈，遇到右括号‘)’, ']', '}'时，则与栈顶元素比较，如果是匹配的，则直接将栈顶元素出栈，如果栈为空或者不匹配，则直接返回False。括号字符串遍历结束后，还需要检查栈是否为空，为空才表示是一个合法的括号组合。

技巧：

使用map，以右括号为key，左括号为value，可以减少代码量。

C++

class Solution {
    public:    bool isValid(string s) {        stack
    
      st;        unordered_map
     
       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
    
      st = new Stack
     
      ();        HashMap
      
        map = new HashMap
       
        (){
   {            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复制代码