要成功就做一百题-93

题目名称

有效的括号判断

描述

输入的字符串只包含{ [] } ()三种括号的组合,判断输入是否是有效的括号,如下:

//
// 注意空字符串可被认为是有效字符串。 
//
// 示例 1: 
//
// 输入: "()"
//输出: true
// 
//
// 示例 2: 
//
// 输入: "()[]{}"
//输出: true
// 
//
// 示例 3: 
//
// 输入: "(]"
//输出: false
// 
//
// 示例 4: 
//
// 输入: "([)]"
//输出: false
// 
//
// 示例 5: 
//
// 输入: "{[]}"
//输出: true 

解题思路

这里重点就是要判断括号是否是匹配的，比如找到{，就判断对应的}是否存在，但是这样有个问题是比如中间有其他括号，也得判断，整个操作感觉会变得复杂。
换个思路，举一种类型括号的例子。先放一个堆栈，遍历字符串，如果栈是空的或者遍历元素是左括号{，就放进去，遍历到}，即右括号的时候，再看看栈中是否有对应左括号{，有的话把左括号放出来，没有就表示非合格的括号，直接返回false，这样一个括号的匹配就完成了，有点倒着处理的意思。最终的栈仍然是空的。

代码

  Map<Character, Character> map = new HashMap<>();
    Set<Character> left = new HashSet<>();
       map.put(')', '(');
            map.put(']', '[');
            map.put('}', '{');
            map.put('(', ')');
            map.put('[', ']');
            map.put('{', '}');
            left.add('[');
            left.add('(');
            left.add('{');
public boolean isValid(String s) {
        if (null == s || "".equals(s)) {
            return true;
        }

        //栈空往里放，不空配对看
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (stack.isEmpty() || left.contains(ch)) {
                stack.push(ch);
            } else {
                char other = stack.peek();
                if (map.get(ch) != null && other == map.get(ch)) {
                    stack.pop();
                }else {
                    return false;
                }
            }
        }
        return stack.size() == 0;
    }

总结

之前还有一种解法，用switch，也能实现，稍微繁琐点，如下供参考。

 public boolean isValid(String s) {
         Stack<Character> stack = new Stack<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            switch (ch) {
                case '(':
                    stack.push(ch);
                    break;
                case ')':
                    if (!stack.isEmpty() && stack.peek()=='(') {
                        stack.pop();
                    }else {
                        stack.push(ch);
                    }
                    break;
                case '{':
                    stack.push(ch);
                    break;
                case '}':
                    if (!stack.isEmpty() && stack.peek() == '{') {
                        stack.pop();
                    }else {
                        stack.push(ch);
                    }
                    break;
                case '[':
                    stack.push(ch);
                    break;
                case ']':
                    if (!stack.isEmpty() && stack.peek() == '[') {
                        stack.pop();
                    }else {
                        stack.push(ch);
                    }
                    break;
                    default:
                        return false;
            }
        }
        return stack.isEmpty();
    }