給定一個(gè)只包括 '('，')'山析，'{'堰燎，'}'，'['笋轨，']' 的字符串秆剪，判斷字符串是否有效。
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合爵政。
左括號(hào)必須以正確的順序閉合仅讽。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
- show the code1:
class Solution:
def isValid(self, s: str) -> bool:
while '()' in s or '[]' in s or '{}' in s:
s = s.replace('()','')
s = s.replace('[]','')
s = s.replace('{}','')
return s==''
- show the code2:
class Solution:
def isValid(self, s: str) -> bool:
if not s:
return True
if s[0]==']' or s[0]==')' or s[0]=='}':
return False
res = []
for i in s:
if i == '[' or i == '(' or i == '{':
res.append(i)
elif res and res[-1] == '[' and i == ']':
res.pop()
elif res and res[-1] == '(' and i == ')':
res.pop()
elif res and res[-1] == '{' and i == '}':
res.pop()
else:
return False
return not res
- show the code3:
class Solution:
def isValid(self, s: str) -> bool:
res,dic = [],{']':'[',')':'(','}':'{'}
for i in s:
if i in dic:
ii = res.pop() if res else 'error'
if ii != dic[i]:
return False
else:
res.append(i)
return not res
- 上面三種方法中钾挟，法一算是比較bug的方法洁灵，用python還是很簡(jiǎn)單的，直接使用replace函數(shù)就好了掺出。
- 第二三中方法是一樣的思路徽千，利用棧的先進(jìn)后出來(lái)做，按照題目的要求汤锨，我們知道開(kāi)括號(hào)閉括號(hào)必須順序合格双抽，這意味著開(kāi)括號(hào)后面必須接閉括號(hào)，而且要是同一類型的
- code2稍微繁瑣了一些闲礼，相當(dāng)于考慮到了所有情況牍汹，比如空字符串有效铐维，以閉括號(hào)開(kāi)頭的字符串無(wú)效。
- code3則是code2的改進(jìn)柑贞，我們可以考慮利用一個(gè)字典來(lái)存儲(chǔ)閉括號(hào)和其對(duì)應(yīng)的開(kāi)括號(hào)方椎，這樣就不用像code2那樣枚舉所有的情況了，代碼簡(jiǎn)單化了很多钧嘶，這里 充分體現(xiàn)了耗費(fèi)一定的空間來(lái)存儲(chǔ)變量的好處棠众，特別是像字典（哈希表）這樣的數(shù)據(jù)結(jié)構(gòu)。
