問題描述
給定一個只包括'('燃异，')'携狭，'{'，'}'回俐，'['逛腿，']'的字符串，判定字符串是否有效仅颇。
有效字符串需滿足：
- 左括號必須用想同類型的右括號閉合单默。
- 左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串忘瓦。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
解題思路
之前沒怎么刷過算法題搁廓，所以參考了下別人的代碼，大致都是通過遍歷字符串中的字符，首先將"(""{""["這三種字符壓進棧境蜕，當遇到")""{""["這三種字符時蝙场，進行出棧操作，將出棧后的字符與遇到的字符做匹配粱年，如匹配成功則算法繼續(xù)運行售滤，當匹配不成功時則退出算法返回False。
另外台诗，在自己實現(xiàn)算法時發(fā)現(xiàn)經(jīng)常需要判斷棧是否為空完箩，有時候棧不為空時卻返回了字符串為正確的結(jié)果，在自己做題時還是需要注意到這些細節(jié)的拉队。
具體代碼
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
i = 0
stack = []
while i < len(s):
if s[i] == "[" or s[i] == "{" or s[i] == "(":
stack.append(s[i])
elif s[i] == "]" and stack: #判定棧是否為空
if stack[-1] == "[":
stack.pop()
else:
break
elif s[i] == "}" and stack:
if stack[-1] == "{":
stack.pop()
else:
break
elif s[i] == ")" and stack:
if stack[-1] == "(":
stack.pop()
else:
break
else:#這種情況是棧為空或者遇到其他符號
break
i += 1
if i == len(s) and not stack:#棧為空時才算正確
return True
else:
return False
