LeetCode.020.Valid Parentheses 括号匹配

题目描述

020 Valid Parentheses
https://leetcode-cn.com/problems/valid-parentheses/
https://leetcode.com/problems/valid-parentheses/description/

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

---

相似题目

LeetCode.020.Valid Parentheses 括号匹配
LeetCode.032.Longest Valid Parentheses 最长有效括号

---

解题过程

括号匹配，一看就知道是用栈，遇到左括号入栈，遇到右括号出栈匹配，不过还是有需要注意的地方，比方说匹配过程中如果栈为空则错误（右括号多），匹配完成后栈不空也是错误的（左括号多）。

private static class SolutionV2018 {
    public boolean isValid(String s) {
        Stack<String> stack = new Stack<String>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                switch (ch) {
                    case '(':
                        stack.push(")"); break;
                    case '[':
                        stack.push("]"); break;
                    case '{':
                        stack.push("}"); break;
                    default:
                        break;
                }
            } else {
                if (stack.isEmpty()) {//中途栈为空说明不匹配
                    return false;
                } else if (!stack.pop().equals(s.substring(i, i + 1))) {
                    return false;
                }
            }
        }
        return stack.isEmpty() ? true : false;//最后栈为空才匹配
    }
}

我的代码速度不快，我看速度快的基本上都是用数组模拟栈，而不是直接用Java中的Stack。

---

GitHub代码

algorithms/leetcode/leetcode/_020_ValidParentheses.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_020_ValidParentheses.java

---