20. Valid Parentheses

解法一

思路

最直接的想法是利用栈。
遍历字符串，对于左括号入栈。
如果遇到右括号，将最近入栈的字符出栈，如果不匹配，返回 false；
如果数组遍历完了，栈也为空，未出现不匹配就返回 true;
其中会遇到几个情况需要解决，比如空字符串返回 true；比如要保证 pop() 时栈内得有元素等

代码

class Solution {
    public boolean isValid(String s) {
        if (s.length() == 0 || s == null) return true;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '{') {
                // 入栈
                stack.push(s.charAt(i));
            } else {
                if (stack.size() != 0) {
                    char c = stack.pop();
                    if (c == '{' && s.charAt(i) != '}') return false;
                    else if (c == '[' && s.charAt(i) != ']') return false;
                    else if (c == '(' && s.charAt(i) != ')') return false;
                } else {
                    return false; // In this case the there is no left parentheses in stack, but there still is a right one at i
                }
            }
        }
        if (stack.isEmpty()) {
            return true; // All pairs are formed.
        }
        return false;
    }
}

复杂度分析

• 时间复杂度
  O(n)
• 空间复杂度
  O(n)

解法二

思路

此题还有一个更为聪明的做法，使代码更加简洁。我们知道，如果要匹配，出现一个左括号必须再出现一个右括号。那么我们可以在出现左括号时入栈相应的右括号。由于栈后进先出，如果配对，在遇到左括号后出现的一定是对应的右括号。这时，我们仅需将刚刚入栈在栈顶的右括号取出判断是否是对应的右括号即可。
另外，所有括号必须成对。如果最后栈非空，那一定是有未成对的括号出现，返回 false。

代码

class Solution {
    public boolean isValid(String s) {
        if (s.length() == 0 || s == null) {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        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();
    }
}

复杂度分析

• 时间复杂度
  O(n)
• 空间复杂度
  O(n)

本作品采用《CC 协议》，转载必须注明作者和本文链接