目錄鏈接：http://m.itdecent.cn/p/9c0ada9e0ede
有效的括號(hào)
有效的括號(hào)（Valid Parentheses）
給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。
有效字符串需滿足：
左括號(hào)必須用相同類型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
切題
一、Clarification
沒(méi)有特別需要注意的邊界問(wèn)題，字符串結(jié)束后注意判斷是否所有左右括號(hào)都匹配（借助棧，就是看最后存放右邊括號(hào)的棧是否為空）
二、Possible Solution
1、借助棧
對(duì)于所有左邊括號(hào)" ("、"["、"{"，我們無(wú)法直接判斷是否合法，將其入棧stack；對(duì)于右邊括號(hào)"）" 、"]"、"}"，我們從棧stack頂取出數(shù)據(jù)（如果為空匹配失敗為無(wú)效括號(hào)），并判斷是否是與右邊括號(hào)相匹配的左邊括號(hào)，是當(dāng)前匹配成功，不是則匹配失敗為無(wú)效括號(hào)，如果到了字符串結(jié)束，棧stack不為空也匹配失敗為無(wú)效括號(hào)，棧stack為空所有匹配成功為有效括號(hào)。
時(shí)間復(fù)雜度： O(n)
Python3 實(shí)現(xiàn)
堆棧 + 字典
有效的括號(hào)(Valid Parentheses) Py3 堆棧 + 字典實(shí)現(xiàn)
class Solution:
def isValid(self, s: str) -> bool:
stack = []
paren_dict = {')':'(',']':'[','}':'{'} #有配對(duì)情況 可以使用dict存儲(chǔ)其鍵值對(duì)
for c in s:
if c not in paren_dict: #右括號(hào)類型 入棧
stack.append(c)
elif not stack: #如果這時(shí)棧已經(jīng)空了 無(wú)效 注這個(gè)判斷需要在下一個(gè)判斷之前
return False
elif stack.pop()!= paren_dict[c]: #左括號(hào)類型 其paren_dict對(duì)應(yīng)值需要與棧頂元素匹配
return False
return not stack #s遍歷完了 如果為空棧 有效 否則為無(wú)效
Java實(shí)現(xiàn)
堆棧 + map
其解題思路同Python3一樣
有效的括號(hào)(Valid Parentheses) Java堆棧 + map實(shí)現(xiàn)
C++實(shí)現(xiàn)
堆棧 + map
有效的括號(hào)(Valid Parentheses) C++堆棧 + map實(shí)現(xiàn)
GitHub鏈接：
https://github.com/lichangke/LeetCode
知乎個(gè)人首頁(yè)：
https://www.zhihu.com/people/lichangke/
簡(jiǎn)書個(gè)人首頁(yè)：
http://m.itdecent.cn/u/3e95c7555dc7
個(gè)人Blog:
https://lichangke.github.io/
歡迎大家來(lái)一起交流學(xué)習(xí)
