转载

20. Valid Parentheses

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

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

难度：easy

题目：

给定仅包含字符'(', ')', '{', '}', '[' 和 ']'的字符串, 判定这个字符串是否有效。

输入字符串是否有效：

开括号必需与同类型括号关闭。

开括号必需要以正确的顺序关闭。

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

思路：stack

Runtime: 5 ms, faster than 74.68% of Java online submissions for Valid Parentheses.

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

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

原文 https://segmentfault.com/a/1190000018091854

正文到此结束