题目

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

有效字符串需满足：

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

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

题解

大学课本级题目

时间复杂度：O(n)，n=String.length()

空间复杂度：O(1)

实现

public boolean isValid(String s) {
           // 字符数组        // 左括号入栈        // 右括号pop，匹配不上pass        int len = s.length();        if(len % 2 == 1) {
               return false;        }        Map
   
     matchMap = new HashMap<>() {
               {
                   put(')','(');                put(']','[');                put('}','{');            }        };        // 接口思想：使用Deque接收让List表现的像个队列，但deque不是list        Deque
    
      stack = new LinkedList<>();        for(int i=0; i < len; i++) {
               Character ch = s.charAt(i);            if(matchMap.containsKey(ch)) {
                   if(matchMap.isEmpty() || stack.peek() != matchMap.get(ch)) {
                       return false;                }                stack.pop();            }else {
                   stack.push(ch);            }        }        return stack.isEmpty();    }

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

你可能感兴趣的文章