有效的括号


力扣连接:有效的括号

题目描述:

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

有效字符串需满足:

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

实例:

  • "()[]{}" - true
  • "(]" - false
  • "([)]" - false
  • "{[]}" - true

思路:

首先想到暴力解决,发现逻辑写着写着就写不下去了,情况还挺复杂,最后参考了官方解法,使用栈的方式可以巧妙的解决。这种就属于技巧型的题目。

从题目中先找规律,如果是和一个合法的串,会发现两个重要的规律:

  1. 第一个闭括号的前一个字符一定是它的开括号
  2. 剔除找到的第一个有效的括号对,剩下的串应该也是合法的

这样的话就可以去搜索第一个闭括号,判断其前一个字符是不是其开括号,如果不是直接返回 false,如果是则从整个串里剔除这对继续判断剩余的,如果到最后串全部剔除了,说明整个串就是一个合法有效的括号。

代码具体怎么实现呢?我们可以使用一个 list 去维护这个不断减少的串,应该也可以实现,但是这里更适合一种特殊的 list 结构,那就是不经常使用的栈 Stack。

使用栈的话,遍历字符数组,遇到开括号压入栈,遇到闭括号则从栈顶取一个元素比较是不是一对,如果不是返回 false,如果是则弹出栈顶元素继续比较。

class Solution {
    private static Map<Character, Character> map = new HashMap<>();
    static {
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
    }
    public boolean isValid(String s) {
        if (s==null || s=="")
            return false;
        int len = s.length();
        if (len%2 != 0)
            return false; //合法的肯定为偶数个
        //使用栈的思路解决,规律是:1.如果是和一个合法的串,则第一个闭括号的前一个字符一定是它的开括号;2. 剔除找到的第一个有效的括号对,剩下的串应该也是合法的;典型的使用栈的场景
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < len; i++) {
            if (map.keySet().contains(chars[i])){
                stack.push(chars[i]);
            }else {
                if (i>0 && chars[i] == map.get(stack.pop()))
                    continue;
                return false;
            }
        }
        return stack.isEmpty();
    }
}
Copyright © jverson.com 2019 all right reserved,powered by Gitbook 13:17:08

results matching ""

    No results matching ""