【LeetCode】20.Valid Parentheses

1 问题

Given a string s 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.
• Every close bracket has a corresponding open bracket of the same type.

1.1 示例一

Input: s = “()”
Output: true

1.2 示例二

Input: s = “()[]{}”
Output: true

1.3 实例三

Input: s = “(]”
Output: false

提示：

$1 \leq s.length \leq 10^4$
s consists of parentheses only ‘()[]{}’.

2 解题思路

2.1 解法一

利用栈，

• 如果遍历字符串s中的符号为(、[、{其中之一，则放入栈中；
• 否则，只要栈不为空，栈顶符号与当前遍历符号是上述三种之一的匹配得上，则出栈
• 否则，其他情况均不合法。

详见代码中的解法一。

2.2 解法二

该方法取自LeetCode外站的大神，巧妙地运用栈，完美解决，且时间复杂度，代码复杂度均非常优秀。思想其实与解法一相同。

3 代码

class Solution {
    //解法一：栈
    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<Character>();
        char top;
        // Loop
        for (char c : s.toCharArray()) {
            // if c is an open bracket, like '(','[' or '{', then push it into stack
            if ('(' == c || '[' == c || '{' == c) {
                stack.push(c);
            } else {
                // if the stack is empty, there is no matching open bracket, so return false
                if (stack.isEmpty()) {
                    return false;
                }
                // pop the top character and check if it's the matching open bracket
                top = stack.peek();
                if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) {
                    // if it is, pop the open bracket from the stack
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        // If the stack is empty, all opening brackets have been closed, so return true
        // Otherwise, there are unmatched opening brackets, so return false
        return stack.isEmpty();
    }

    public boolean isValid(String s) {

        if (s.length() % 2 == 1)
            return false;

        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(')');
            } else if (s.charAt(i) == '{') {
                stack.push('}');
            } else if (s.charAt(i) == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != s.charAt(i))
                return false;
        }
        return stack.isEmpty();
    }
}