当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.020.Valid Parentheses 括号匹配

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


上一篇 Hexo博客(21)创建博客概览插件

下一篇 LeetCode.021.Merge Two Sorted Lists 合并两个有序链表

阅读
评论
298
阅读预计1分钟
创建日期 2018-02-10
修改日期 2018-02-12
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论