給定一個只包括 '('煌寇，')'，'{'逾雄，'}'阀溶，'['，']' 的字符串鸦泳，判斷字符串是否有效银锻。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合做鹰。
注意空字符串可被認(rèn)為是有效字符串击纬。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
思路
想象一下，你正在為你的大學(xué)課設(shè)編寫一個小型編譯器钾麸，編譯器的任務(wù)之一（或稱子任務(wù)）將檢測括號是否匹配更振。
我們本文中看到的算法可用于處理編譯器正在編譯的程序中的所有括號，并檢查是否所有括號都已配對饭尝。這將檢查給定的括號字符串是否有效肯腕，是一個重要的編程問題。
我們這個問題中將要處理的表達(dá)式可以包含以下三種不同類型的括號：
-
()钥平， -
{}以及 []
在查看如何檢查由這些括號組成的給定表達(dá)式是否有效之前实撒，讓我們看一下該問題的簡化版本，在簡化后的問題中涉瘾，只含一種類型的括號奈惑。這么一來，我們將會遇到的表達(dá)式是
(((((()))))) -- VALID
()()()() -- VALID
(((((((() -- INVALID
((()(()))) -- VALID
上我們試著用一個簡單的算法來解決這一問題睡汹。
- 我們從表達(dá)式的左側(cè)開始肴甸，每次只處理一個括號。
- 假設(shè)我們遇到一個開括號（即
(）囚巴，表達(dá)式是否無效取決于在該表達(dá)式的其余部分的某處是否有相匹配的閉括號（即)）原在。此時，我們只是增加計數(shù)器的值保持跟蹤現(xiàn)在為止開括號的數(shù)目彤叉。left += 1 - 如果我們遇到一個閉括號庶柿，這可能意味著這樣兩種情況：
- 此閉括號沒有與與之對應(yīng)的開括號，在這種情況下秽浇，我們的表達(dá)式無效浮庐。當(dāng)
left == 0，也就是沒有未配對的左括號可用時就是這種情況。 - 我們有一些未配對的開括號可以與該閉括號配對审残。當(dāng)
left > 0梭域，也就是有未配對的左括號可用時就是這種情況。
- 此閉括號沒有與與之對應(yīng)的開括號，在這種情況下秽浇，我們的表達(dá)式無效浮庐。當(dāng)
- 如果我們在
left == 0時遇到一個閉括號（例如)）搅轿，那么當(dāng)前的表達(dá)式無效病涨。否則，我們會減少left的值璧坟，也就是減少了可用的未配對的左括號的數(shù)量既穆。 - 繼續(xù)處理字符串，直到處理完所有括號雀鹃。
- 如果最后我們?nèi)匀挥形磁鋵Φ淖罄ㄌ柣霉ぃ@意味著表達(dá)式無效。
在這里討論這個特定算法是因為我們從該解決方案中獲得靈感以解決原始問題黎茎。為了更好地理解我們討論的算法会钝，請觀看下面的動畫演示。
1 / 12
如果我們只是嘗試對原始問題采用相同的辦法工三，這是根本就行不通的迁酸。基于簡單計數(shù)器的方法能夠在上面完美運行是因為所有括號都具有相同的類型俭正。因此奸鬓，當(dāng)我們遇到一個閉括號時，我們只需要假設(shè)有一個對應(yīng)匹配的開括號是可用的掸读，即假設(shè) left > 0串远。
但是，在我們的問題中儿惫，如果我們遇到 ]澡罚，我們真的不知道是否有相應(yīng)的 [ 可用。你可能會問：
為什么不為不同類型的括號分別維護(hù)一個單獨的計數(shù)器肾请？
這可能不起作用留搔，因為括號的相對位置在這里也很重要。例如：
如果我們只是在這里維持計數(shù)器铛铁，那么只要我們遇到閉合方括號隔显，我們就會知道此處有一個可用的未配對的開口方括號。但是饵逐，最近的未配對的開括號是一個花括號括眠，而不是一個方括號，因此計數(shù)方法在這里被打破了倍权。
方法：棧
關(guān)于有效括號表達(dá)式的一個有趣屬性是有效表達(dá)式的子表達(dá)式也應(yīng)該是有效表達(dá)式掷豺。（不是每個子表達(dá)式）
此外，如果仔細(xì)查看上述結(jié)構(gòu)，顏色標(biāo)識的單元格將標(biāo)記開閉的括號對当船。整個表達(dá)式是有效的题画，而它的子表達(dá)式本身也是有效的。這為問題提供了一種遞歸結(jié)構(gòu)生年。例如婴程，考慮上圖中兩個綠色括號內(nèi)的表達(dá)式廓奕。開括號位于索引 1抱婉，相應(yīng)閉括號位于索引 6。
如果每當(dāng)我們在表達(dá)式中遇到一對匹配的括號時桌粉，我們只是從表達(dá)式中刪除它蒸绩，會發(fā)生什么？
讓我們看看下面的這個想法铃肯，從整體表達(dá)式中一次刪除一個較小的表達(dá)式患亿，因為這是一個有效的表達(dá)式，我們最后剩留下一個空字符串。
1 / 5
在表示問題的遞歸結(jié)構(gòu)時，棧數(shù)據(jù)結(jié)構(gòu)可以派上用場谱轨。我們無法真正地從內(nèi)到外處理這個問題衷畦，因為我們對整體結(jié)構(gòu)一無所知。但是植酥，棧可以幫助我們遞歸地處理這種情況，即從外部到內(nèi)部雾消。
讓我們看看使用棧作為該問題的中間數(shù)據(jù)結(jié)構(gòu)的算法。
算法
- 初始化棧 S挫望。
- 一次處理表達(dá)式的每個括號立润。
- 如果遇到開括號，我們只需將其推到棧上即可媳板。這意味著我們將稍后處理它桑腮，讓我們簡單地轉(zhuǎn)到前面的 子表達(dá)式。
- 如果我們遇到一個閉括號蛉幸，那么我們檢查棧頂?shù)脑氐降Ｈ绻麠ｍ數(shù)脑厥且粋€
相同類型的左括號，那么我們將它從棧中彈出并繼續(xù)處理巨缘。否則添忘，這意味著表達(dá)式無效。 - 如果到最后我們剩下的棧中仍然有元素若锁，那么這意味著表達(dá)式無效搁骑。
我們來看一下該算法的動畫演示，然后轉(zhuǎn)到實現(xiàn)部分。
現(xiàn)在讓我們看看該算法是如何實現(xiàn)的仲器。
Java版本
class Solution {
// Hash table that takes care of the mappings.
private HashMap<Character, Character> mappings;
// Initialize hash map with mappings. This simply makes the code easier to read.
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
// Initialize a stack to be used in the algorithm.
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// If the current character is a closing bracket.
if (this.mappings.containsKey(c)) {
// Get the top element of the stack. If the stack is empty, set a dummy value of '#'
char topElement = stack.empty() ? '#' : stack.pop();
// If the mapping for this bracket doesn't match the stack's top element, return false.
if (topElement != this.mappings.get(c)) {
return false;
}
} else {
// If it was an opening bracket, push to the stack.
stack.push(c);
}
}
// If the stack still contains elements, then it is an invalid expression.
return stack.isEmpty();
}
}
GO 語言版本如下:
package valid_parentheses
func isValid(str string) bool {
s := new(stack)
for _, b := range str {
switch b {
case '(', '[', '{':
s.push(b)
case ')', ']', '}':
if r, ok := s.pop(); !ok || r != matching[b] {
return false
}
}
}
if len(*s) > 0 {
return false
}
return true
}
var matching = map[rune]rune{
')': '(',
']': '[',
'}': '{',
}
type stack []rune
func (s *stack) push(b rune) {
*s = append(*s, b)
}
func (s *stack) pop() (rune, bool) {
if len(*s) > 0 {
res := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return res, true
}
return 0, false
}
