LeetCode *20.Valid Parentheses (Python Solution)

问题描述

Valid Parentheses Leetcode20
Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:
1.Open brackets must be closed by the same type of brackets.
2.Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

给定一个只包含字符’（’，’）’，’{’，’}’，’[‘和’]'的字符串，确定输入字符串是否有效。

如果输入字符串有效：
1.打开括号必须用相同类型的括号封闭。
2.必须以正确的顺序关闭打开括号。
请注意，空字符串也被视为有效。

Python Solution

本文从两个角度来解读这道题，解法一是简单判定法，解法二是字典建立对应关系，面试推荐第二种。

Solution 1 (简单判定)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if i in '({[':
                stack.append(i)
            else:
                if i == ']':
                    if not stack or stack[-1] != '[':
                        return False
                    else:
                        stack.pop()
                elif i == '}':
                    if not stack or stack[-1] != '{':
                        return False
                    else:
                        stack.pop()
                else:
                    if not stack or stack[-1] != '(':
                        return False
                    else:
                        stack.pop()
        if not stack:
            return True

最简单的判定法，根据的是栈的思想。如果是左括号，入栈，是右括号进行判定是不是匹配，匹配则出栈，不匹配则False。最后判断栈内是否为空。

时间复杂度O(n)，空间复杂度O(n)。

Solution 2 (构建字典建立对应关系)

class Solution(object):
    def isValid(self, s):
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}
        
        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        return not stack

也是栈的思想，不过通过字典建立了对应关系，提高了效率。

时间复杂度 O(n)，空间复杂度O(n)。