LeetCode第20題：有效的括號
1.題目描述
給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，
有效字串需滿足：
1.左括號必須用相同型別的右括號閉合，
2.左括號必須以正確的順序閉合，
- 注：空字符也為有效字符哦（空對空也是一組）
示例：
輸入:'()'
輸出:ture
輸入:'([{}])'
輸出:ture
輸入:'{}])'
輸出:false
輸入:'([)]'
輸出:false
輸入:'([{()})]'
輸出:false
2.解題思路
題目意思是給定一串括號的字符，要你判斷該字串中的括號閉合順序是否一樣和順序是否正確，
我們可以把該字串拆分成兩部分，一部分是左邊的括號，一部分是右邊的括號，
首先，我們來分析一下特殊情況，
第一，肯定是當這個字串是空時，應該回傳ture
第二，如果該字串不對稱，那肯定回傳false
然后，我們會想怎么讓字串中的這些括號進行匹配
那這里就要用到我們的堆疊了，
堆疊是一種特殊的字串，它里面的元素是‘先進后出’，為了方便理解，看下圖
- 實作程序：
1.初始化一個堆疊stack，
2.用for回圈把字串遍歷出來放入新陣列中，并且找出左括號的字符把它放進堆疊中，此時字串中只剩下右括號了，
3.我們把堆疊里的元素取出來去比較右括號，如果沒有匹配的就回傳false
要注意兩種情況：1.當字串像’{}])’ 這時我們會發現當回圈一次后，第二次回圈堆疊里已經沒有元素了，而右括號還有元素，這時我們應該怎么辦？所以判斷條件我們應該加上當堆疊的長度不存在回傳false
2.當字串內的括號完全匹配時，像’([{}])’ 當回圈結束時，程序3是不會執行的，應該回傳ture
所以我們在回圈體外回傳return !stack.length，！0就相當于1 ， ture
3.代碼實作
由于個人能力有限，暫時只提供JavaScript語言代碼實作，只要理解了本演算法的思想，你也能用其他語言實作出來，這也是對個人代碼能力的鍛煉，
/**
* @author 我叫堅強我不哭
* @param {string} s
* @return {boolean}
*/
const leftToRight = {
"(":")",
"{":"}",
"[":"]"
}
var isValid = function(s) {
if (!s) {
return true
}
// 初始化一個stack堆疊
const stack = []
const len = s.length
for (let i = 0; i < len ;i++) {
// 遇到左括號就入堆疊
// 否則就將堆疊里的元素取出來比較
const ch = s[i]
if (ch == "(" || "{" || "["){
stack.push(leftToRight[ch])
}else {
if (!stack.length || stack.pop() !== ch) {
return false
}
}
}
return !stack.length
};
4.總結
一般涉及到對稱的話，我們優先考慮用堆疊來解決，
前期在刷LeetCode時，如果想了一會兒沒有思路的話不要死扣，應該果斷的去看別人的解題思路，理解了之后，在憑借自己的理解和記憶自己敲一遍，
學習 = 學 + 習，知識是學出來的，不是在自己腦子里蹦出來的；學過之后，還要自己動手練習，新手要勇敢地、經常地學習別人的解法和答案，然后憑理解敲代碼練習，只要度過刷題初期的痛苦，后面就會越刷越快，
- 注：這僅是我自己的理解，如果有更好的方法，歡迎大佬們指點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/278484.html
標籤：其他