Easy, Dynamic Programming
Question
给定string只含 '(', ')', '{', '}', '[', ']'，判断string是否valid
Example: "()[]{}": true
"([)]" : false
Solution
论坛一个coder的方法，做减法，把配对的括号一一去除。想法非常简单，缺点是complexity会比较高。
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if len(s) % 2 != 0:
return False
while "()" in s or "[]" in s or "{}" in s:
s = s.replace("()","").replace("[]","").replace("{}","")
return s == ''
更加有效的方法是利用堆栈。
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
dic = {'(':')','{':'}','[':']'}
stack = []
for c in s:
if c in dic:
stack.append(c)
elif stack == [] or dic[stack.pop()] != c:
return False
return stack == []
