0020. Valid Parentheses.md

题目

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.

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

我的思路

这道题用Java中的栈就可以很容易的解决。Python中没有栈，但是可以通过list的append和pop方法来实现栈的思想。方法很简单，遍历原字符串，遇到“(”、“[”、“{”时就令其入栈，遇到“)”、“]”、“}”就从栈中取出元素并进行比较。遍历完后栈一定为空，否则也返回False。

代码

class Solution:
    def isValid(self, s: str) -> bool:
        l= []
        for ch in s:
            if ch == "(" or ch == "{" or ch == "[":
                l.append(ch)
            else:
                if len(l) == 0:
                    return False
                elif ch == ")":
                    a = l.pop()
                    if a != "(":
                        return False
                elif ch == "]":
                    a = l.pop()
                    if a != "[":
                        return False
                elif ch == "}":
                    a = l.pop()
                    if a != "{":
                        return False
        if len(l) != 0:
            return False
        
        return True

• 复杂度：O(n)

网上方法

看了别人的方法，用字典的方式可以简洁一些，省去很多的if。

代码

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dict={'(':')',
              '{':'}',
             '[':']'}
        
        stack=[]
        
        for i in s:
            if i in dict:
                stack.append(i)
            elif len(stack)==0 or dict[stack.pop()]!=i:
                return False
        if len(stack)==0:
            return True