leetcode 20. 有效的括号

妖狐艹你老母 2022-05-18 03:39 232阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

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

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

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

**示例 1:**

输入: "()"
    输出: true

**示例 2:**

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

**示例 3:**

输入: "(]"
    输出: false

**示例 4:**

输入: "([)]"
    输出: false

**示例 5:**

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

--------------------

class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            a = {')':'(', ']':'[', '}':'{'}
            l = [None]#设置None是为了排除空值的情况！
            for i in s:
                if i in a and a[i] == l[-1]:
                    l.pop()
                else:
                    l.append(i)
            return len(l)==1#用来排除空值的情况

java版本

class Solution {
        public boolean isValid(String s) {
        
            Stack<Character> stack=new Stack<>();                          //Character 类用于对单个字符进行操作
            char[] chs=s.toCharArray();                                    //toCharArray() 方法将字符串转换为字符数组
            int len=chs.length;
            if((len&1)==1)return false;                                    //(len&1)==1 位运算结果为1就是奇数
            for(int i=0;i<len;i++){
                if(stack.isEmpty()||!isMatch(stack.peek(),chs[i]))         //java.util.Stack.peek()方法用于查找在此堆栈顶部的对象，无需从堆栈中取出
                    stack.push(chs[i]);
                else  
                    stack.pop();
            }
            return stack.isEmpty();
        }
        public boolean isMatch(char a,char b){
           switch(a){
                case '(': if(b == ')') return true; else return false;
                case '{': if(b == '}') return true; else return false;
                case '[': if(b == ']') return true; else return false;
                default : return false;
            }
     
        }
    }

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test