leetcode算法題解 20題 python Ver.
題目
給定一個只包括 '('，')'竞川，'{'，'}'叁熔，'['委乌，']' 的字符串，判斷字符串是否有效荣回。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合遭贸。
左括號必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串心软。
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/valid-parentheses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有壕吹。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處删铃。
思路
這個問題可以用堆棧的思路來解決耳贬，遍歷字符串，把左括號不斷的壓入棧中泳姐，直到遇見右括號效拭，去棧中判斷最后一個被壓入的左括號是否是對應(yīng)的右括號，如果不是胖秒，返回False缎患。最后查看棧中是否還有括號，如果有阎肝，那么返回False挤渔；如果沒有，那么返回True风题。
由于python中的list數(shù)據(jù)類型判导，可以直接當(dāng)做棧來使用嫉父。使用到的屬性為：append（即為入棧），pop（即為出棧）眼刃，其中l(wèi)ist[-1]為棧頂绕辖，list[0]為棧底。
解答
情況分析
當(dāng)字符串為空時(shí)
按照題意擂红，應(yīng)該是有效的仪际。
if len(s) == 0:
return True
當(dāng)字符串中只有右括號時(shí)
此時(shí)，棧為空昵骤，也會觸發(fā)有效树碱。所以應(yīng)該加上一個判斷條件來避免判斷錯誤。
Sstack = []#list為棧
length = 0
if i == '{' or i == '(' or i =='[':
Sstack.append(i)#將括號壓入棧中
else:
length += 1#記錄右括號的數(shù)量
當(dāng)字符串中右括號比左括號多時(shí)
例如：'{}()]]'
此時(shí)length這個變量起到作用变秦，每出棧一個左括號成榜，length就減1，當(dāng)length=0且棧中元素為空同時(shí)滿足時(shí)蹦玫，便可以判定有效了赎婚。
代碼
class Solution:
def isValid(self, s: str) -> bool:
Sstack = []
length = 0
if len(s) == 0:
return True
for i in s:
if i == '{' or i == '(' or i =='[':
Sstack.append(i)
else:
length += 1
if len(Sstack) != 0:
if i == '}' and Sstack[-1] == '{':
Sstack.pop()
length -= 1
if i == ']' and Sstack[-1] == '[':
Sstack.pop()
length -= 1
if i == ')' and Sstack[-1] == '(':
Sstack.pop()
length -= 1
return len(Sstack) == 0 and length == 0
通過截圖
復(fù)雜度
由于入棧出棧均為O(1)時(shí)間，整個程序僅有一個循環(huán)钳垮，所以時(shí)間復(fù)雜度應(yīng)該為O(n)
聯(lián)系方式
感謝閱讀惑淳！如果您對本片博文有任何意見或者建議额港，請聯(lián)系我饺窿。感謝不盡??
