本文共 991 字，大约阅读时间需要 3 分钟。

解题思路

我们可以用栈来解决这题，因为栈是先进后出，和这题的要求刚好一致，如果遇到左括号就直接入栈，遇到右括号，就判断栈顶的括号是否为该右括号相对应的左括号，如果不匹配就返回false，匹配就把栈顶元素弹出，然后开始下一个元素的判断；

代码

class Solution {       Map
   
     map = new HashMap<>() {      //保存要匹配的左右括号，可以快速匹配        {               put('(',')');            put('{','}');            put('[',']');        }    };    public boolean isValid(String s) {           Deque
    
      stack = new LinkedList<>();    //用双端队列模拟战        for(char i : s.toCharArray()) {            //把s转为char数组，然后遍历            if(map.containsKey(i))              //判断是不是左括号，是左括号就入栈                stack.push(i);            //判断右括号是否和栈顶为匹配的左括号,匹配就直接弹出栈顶的左括号;                //不匹配就直接返回false； 因为要弹出栈顶所以先要判断栈是否为空            else if(stack.isEmpty() || i != map.get(stack.pop()))                   return false;        }        return stack.isEmpty(); //栈空就代表完全匹配成功，返回true；                                    //不为空就返回false，代表栈还有左括号；    }}
    
   

复杂度分析

• 时间复杂度 ：O(N)
• 空间复杂度 ：O(N)

转载地址：http://yaynz.baihongyu.com/