LEETCODE 20. Valid Parentheses 解题思路分析

题目大意：

有效的括号

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=20

解题思路分析：

本题是经典的Stack应用场景。遍历整个字符串，当遇到正括号时，将其插入进Stack，遇到反括号时，查看Stack的尾部是否是与之对应的正括号，如果是，将Stack尾部正括号pop出栈，反之说明不是有效括号，直接返回false。

循环完整个字符串后，查看Stack中的元素个数，如果为0，说明是有效括号，如果不为0，说明不是，返回false。

实现代码：

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

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 98.55% of Java online submissions for Valid Parentheses.

Memory Usage: 37.3 MB, less than 5.06% of Java online submissions for Valid Parentheses.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-20-valid-parentheses-解题思路分析/