leetcode 20. Valid Parentheses

青旅半醒 2023-07-18 02:17 17阅读 0赞

[https://leetcode.com/problems/valid-parentheses/][https_leetcode.com_problems_valid-parentheses]

给定一个包含字符'(', ')', '\{', '\}', '\[', '\]'的字符串，判断它是否合法，即括号是否正确匹配。注意空字符串也是合法的。

## 一、问题分析 ##

测试用例：

Example 1:
    Input: "()"
    Output: true
    
    Example 2:
    Input: "()[]{}"
    Output: true
    
    Example 3:
    Input: "(]"
    Output: false
    
    Example 4:
    Input: "([)]"
    Output: false
    
    Example 5:
    Input: "{[]}"
    Output: true

一个输入为合法意味着：

1）开括号必须用相同类型的闭括号关闭；

2）开括号关闭的顺序正确

新建一个栈，逢左括号入栈，逢右括号出栈并判断是否与当前字符匹配。

## 二、代码实现 ##

class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            for (int i=0; i<s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == '(' || ch == '{' || ch == '[') {
                    stack.push(ch);
                } else {
                    //"]"
                    if (stack.empty()) {
                        return false;
                    }
                    boolean flag = isMatched(ch, stack.pop());
                    if (flag == false) {
                        return false;
                    }
                }
            }
            
            return stack.isEmpty() ? true : false;
        }
    
        private boolean isMatched(char ch, char target) {
            if ((ch == ')' && target == '(') ||
               (ch == '}' && target == '{')  ||
               (ch == ']' && target == '[') ) {
                return true;
            }    
            return false;
        }
    }

参考：

[https://leetcode.com/problems/valid-parentheses/discuss/9682/Simple-Accepted-Java-solution.][https_leetcode.com_problems_valid-parentheses_discuss_9682_Simple-Accepted-Java-solution.]

[https://leetcode.com/problems/valid-parentheses/discuss/9203/Simple-Python-solution-with-stack][https_leetcode.com_problems_valid-parentheses_discuss_9203_Simple-Python-solution-with-stack]

[https://leetcode.com/problems/valid-parentheses/discuss/9252/2ms-C%2B%2B-sloution][https_leetcode.com_problems_valid-parentheses_discuss_9252_2ms-C_2B_2B-sloution]

[https://leetcode.com/problems/valid-parentheses/discuss/9187/12-lines-of-Java][https_leetcode.com_problems_valid-parentheses_discuss_9187_12-lines-of-Java]

[https_leetcode.com_problems_valid-parentheses]: https://leetcode.com/problems/valid-parentheses/
[https_leetcode.com_problems_valid-parentheses_discuss_9682_Simple-Accepted-Java-solution.]: https://leetcode.com/problems/valid-parentheses/discuss/9682/Simple-Accepted-Java-solution.
[https_leetcode.com_problems_valid-parentheses_discuss_9203_Simple-Python-solution-with-stack]: https://leetcode.com/problems/valid-parentheses/discuss/9203/Simple-Python-solution-with-stack
[https_leetcode.com_problems_valid-parentheses_discuss_9252_2ms-C_2B_2B-sloution]: https://leetcode.com/problems/valid-parentheses/discuss/9252/2ms-C%2B%2B-sloution
[https_leetcode.com_problems_valid-parentheses_discuss_9187_12-lines-of-Java]: https://leetcode.com/problems/valid-parentheses/discuss/9187/12-lines-of-Java