题目描述

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

给定一个只包含'(', ')', '{', '}', '[' 和 ']' 的字符串，判断输入字符串是否有效。
括号必须以正确的顺序闭合，比如 "()" 和"()[]{}" 是有效的， "(]" 和 "([)]" 无效的

原文地址

思路方法

1.采用一种堆栈的方式，如果遇见的是左括号'(', '{', '[' 则字符入栈 ans，遇见的是右括号')', '}', ']'则 ans 出栈，看出栈的字符与当前右括号是否匹配。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        ans = []

        for i in s:
            if i == "(" or i == "{" or i == "[":
                ans.append(i)
            if i == ")" or i == "}" or i == "]":
                if len(ans) == 0:
                    return False
                tmp = ans.pop()
                if not self.match(tmp, i):
                    return False
        if len(ans) == 0:
            return True
        else:
            return False

    def match(self, s1, s2):
        if s1 == "(" and s2 == ")":
            return True
        if s1 == "[" and s2 == "]":
            return True
        if s1 == "{" and s2 == "}":
            return True

        return False

2.Python 还有一种自己的思路，就是直接使用替代方法，遇见'(', ')', '{', '}', '[' 和 ']'成对匹配的字符则用 ‘’ 替换掉。

def isValid(s):
    delta = len(s)

    while(delta != 0 and delta %2 == 0):
        s = s.replace("()", "")
        s = s.replace("[]", "")
        s = s.replace("{}", "")

        delta = len(s) if delta > len(s) else 0

    return len(s) == 0

知识点

#往数组ans里面追加元素i，加在末尾
ans.append(i)

#删除ans数组末尾元素
ans.pop()
#删除指定索引位置元素
ans.pop(i)

#字符串替换
s.replace()
>>> s='hello python,hello world,hello c++,hello java!'
>>> s.replace('hello','Hello')#将字符串s中的所有'hello'子串，替换成'Hello',返回替换后的字符串，原字符串s不变
'Hello python,Hello world,Hello c++,Hello java!'
>>> s
'hello python,hello world,hello c++,hello java!'
>>> s.replace('hello','Hello',2)#将字符串s中的前2个'hello'子串，替换成'Hello'
'Hello python,Hello world,hello c++,hello java!'
>>> s
'hello python,hello world,hello c++,hello java!'
>>> s.replace('wahaha','haha')#要替换的'wahaha'子串不存在，直接返回原字符串
'hello python,hello world,hello c++,hello java!' 

Python 查看帮助文档：

参考地址