20. Valid Parentheses

Problem

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.

https://leetcode.com/problems/valid-parentheses/

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([])"
Output: true

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Test Cases

1 2	class Solution: def isValid(self, s: str) -> bool:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    ("()", True),
    ("()[]{}", True),
    ("(]", False),
    ("([])", True),

    ("((", False),
    ("))", False),
    ("((())", False),
])
class Test:
    def test_solution(self, s, expected):
        sol = Solution()
        assert sol.isValid(s) == expected

Thoughts

栈的典型使用场景。

从左向右扫描 s，如果当前字符是左括号就入栈，如果是右括号就出栈并判断出栈的括号类型跟当前的是否一致，不一致则 not valid。如果看到右括号时栈为空，not valid。如果最后栈没被清空，也 not valid。

显然如果 s 的长度是奇数，一定 not valid。

时间复杂度和空间复杂度都是 O(n)。

Code

solution.py

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) & 1 == 1:
            return False

        stack = []
        for c in s:
            if c in '({[':
                stack.append(c)
                continue

            if not stack:
                return False
            left = stack.pop()
            if left == '(' and c != ')' or left == '{' and c != '}' or left == '[' and c != ']':
                return False

        return len(stack) == 0

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。