20. Valid Parentheses

[chengchengxu15]

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.

[chengchengxu15]

solution1: use Stack:

time complexity: O(n) space complexity: O(n)

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

        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)

        return not stack

[chengchengxu15]

solution 2: recursive method: complexity O(n^2)

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dic={}
        dic[")"] = "("
        dic["]"] = "["
        dic["}"] = "{"
        if len(s)==0:
            return True
        if len(s)==1:
            return False
        if s[0] in dic:
            return False
        for i in range(1,len(s)):
            if s[i] in dic:
                return (s[i-1] == dic [s[i]]) and self.isValid(s[:i-1]+s[i+1:])
        return False