1. 首页
  2. Leetcode经典148题

leetCode-20-Valid Parentheses

题目描述(简单难度)

leetCode-20-Valid Parentheses

括号匹配问题。

如果只有一种括号,我们完全可以用一个计数器 count ,遍历整个字符串,遇到左括号加 1 ,遇到右括号减 1,遍历结束后,如果 count 等于 0 ,则表示全部匹配。但如果有多种括号,像 ( [ ) ] 这种情况它依旧会得到 0,所以我们需要用其他的方法。

栈!

遍历整个字符串,遇到左括号就入栈,然后遇到和栈顶对应的右括号就出栈,遍历结束后,如果栈为空,就表示全部匹配。

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

        }
    }

    return brackets.empty();
}

时间复杂度:O(n)。

空间复杂度:O(n)。

如果学过数据结构,一定写过计算器,括号匹配问题一定遇到过的。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-20-Valid Parentheses

链接:https://www.javajike.com/article/3157.html

« leetCode-19-Remov-Nth-Node-From-End-of-List
leetCode-21-Merge-Two-Sorted-Lists»

相关推荐

QR code