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

解法

字节跳动提前批视频面试一面的笔试题，没有答好，总结一下：

思路很简单，使用一个栈来记录，如果是左括号就入栈，匹配的右括号就出栈。但是考虑清楚每种情况并不容易，条件的判断很重要。

class Solution:
    def isValid(self, s: str) -> bool:
        maps = dict(zip("([{", ")]}"))
        stack = []

        for c in s:
            if c in maps:
                stack.append(c)
            else:
                if not stack:  # an empty stack with a closing parenthesis.
                    return False

                if maps[stack[-1]] == c:  # stack is not empty and matches.
                    stack.pop()
                else:  # stack is not empty but not matches.
                    return False

        return not stack  # empty stack means all the parenthesis are matching.

这里用一个简单的稍兵就能使问题简化很多：

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) & 1:  # if the length of s is odd, than this string must be invalid.
            return False

        maps = dict(zip("([{", ")]}"))
        maps[0] = None
        stack = [0]

        for c in s:
            if c in maps:
                stack.append(c)
            elif maps[stack[-1]] == c:
                stack.pop()
            else:
                return False

        return len(stack) == 1

只遍历一次，时间复杂度 $O(n)$; 使用了一个栈，最坏情况下((((((((((((()需要额外空间 $O(n)$。