每日一道 LeetCode (6)：有效的括號
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：有效的括號
題目來源：https://leetcode-cn.com/problems/valid-parentheses/
給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。 左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例?2:
輸入: "()[]{}"
輸出: true
示例?3:
輸入: "(]"
輸出: false
示例?4:
輸入: "([)]"
輸出: false
示例?5:
輸入: "{[]}"
輸出: true
解題思路
解題思路？
啊呸，有個 P 的解題思路，我跟你們講哦，這種題沒見過，你就是想不出來。
我自己思索了幾分鐘以后，果斷投降去看答案了，這玩意，不是我這種新手小白搞的定的。
結(jié)果，一看答案秒懂。
整個解題思路是借用了數(shù)據(jù)結(jié)構(gòu)「棧」的「先進后出」的特性。
首先第一件事情還是先思考清楚極限情況，比如如果是空字符串，是可以返回 true ，如果字符串長度是奇數(shù)，那么顯然是無法滿足左右括號的對應關系。
接下來就是核心問題，一個左括號一個右括號，中間還可能隔著千山萬水，如何處理？
使用「棧」結(jié)構(gòu)：
遇到左括號就壓入棧。 遇到右括號就和棧頂?shù)淖罄ㄌ柋葘Γヅ涫≈苯臃祷?false 。 如果匹配成功，則可能是嵌套在其它匹配括號中的，所以此時要將當前棧頂?shù)淖罄ㄌ枏棾觥?/section> 如果最后最終，棧中沒有剩余元素，也就是沒有剩下左括號，說明剛好完成匹配，括號字符串有效。否則匹配失敗，括號字符串無效。
如果上面這一段不好理解，可以借助下面這個動圖（來源：LeetCode）：
代碼實現(xiàn)
有了上面的思路，寫代碼都是小事兒了，先看一個我自己寫的，完全符合上面的邏輯：
public boolean isValid(String s) {
if (s.length() == 0) return true;
if (s.length() % 2 == 1) return false;
Stack stack = new Stack<> ();
for (int i = 0; i < s.length(); i++) {
char charAt = s.charAt(i);
// 如果是左括號，則把字符壓入棧
if (charAt == '(' || charAt == '{' || charAt == '[')
stack.push(charAt);
else {
// 如果此時還有右括號而棧中已無左括號
if (stack.isEmpty()) return false;
// 獲取棧頂?shù)闹?/span>
char top = stack.peek();
// 如果棧頂?shù)闹档扔谟依ㄌ枺瑒t出棧，否則返回 false
if ((top == '{' && charAt == '}') || (top == '(' && charAt == ')') || (top == '[' && charAt == ']'))
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}
里面的注釋已經(jīng)比較清晰了，我就不多解釋了。
接著我看了官方提供的答案，基本上思路和我的代碼保持一致，只是把左右括號放入到了哈希表中，由哈希表來判斷括號是否存在。
private Map map;
// 初始化哈希表
public Solution() {
this.map = new HashMap<> ();
this.map.put(')', '(');
this.map.put('}', '{');
this.map.put(']', '[');
}
public boolean isValid_1(String s) {
if (s.length() == 0) return true;
if (s.length() % 2 == 1) return false;
Stack stack = new Stack<> ();
for (int i = 0; i < s.length(); i++) {
char charAt = s.charAt(i);
// 如果不是右括號，則把字符壓入棧
if (!this.map.containsKey(charAt)) {
stack.push(charAt);
} else {
// 如果此時還有右括號而棧中已無左括號
if (stack.isEmpty()) return false;
// 獲取棧頂?shù)闹?/span>
char top = stack.peek();
// 如果棧頂?shù)闹档扔谟依ㄌ枺瑒t出棧，否則返回 false
if (top == this.map.get(charAt))
stack.pop();
else
return false;
}
}
return stack.empty();
}
因為哈希表中的數(shù)據(jù)太少，而且尋址的次數(shù)也不夠多，所以哈希表的方案看起來還比順次匹配的的方案耗時高。
效率更高的方案有沒有，當然有，直接使用數(shù)組模擬棧的入棧和出棧，這個時間是可以壓縮在 1ms 以內(nèi)的，執(zhí)行時間可以在 Java 的提交中擊敗 100% 的用戶，這個示例我就不寫了，感興趣的同學可以自己寫寫看。
在我翻答案的時候看到一個 1ms 的方案，這個方案是對我前面的那個 2ms 的代碼的優(yōu)化，有點意思，拿出來聊一下：
public boolean isValid_2(String s) {
char[] chs = s.toCharArray();
Stack stack = new Stack<>();
for (char c : chs) {
if (c == '{') {
stack.push('}');
} else if (c == '[') {
stack.push(']');
} else if (c == '(') {
stack.push(')');
} else if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
return stack.isEmpty();
}
這個方案就是在遇到左括號的時候往棧里面放一個對應的右括號，這么做的原因我猜測是為了好判斷，只需要取出的時候和當前循環(huán)的右括號做一次 == 判斷，如果相等就繼續(xù)循環(huán)，不相等就直接返回 false 了。
不得不說這個方案的構(gòu)思很巧妙，在已有的方案上做了相當極致的優(yōu)化，把耗時進一步降低。果然姜還是老的辣，你大爺還是你大爺。
果然是學無止境，希望各位刷 LeetCode 的同學，如果時間充足，也可以多看看不同的答案，對開闊思路和視野真的是相當有幫助。
?順便吐槽下：想到這些方案的大神太 TM 變態(tài)了，這個腦回路和常人差的太遠了，能用數(shù)組把耗時壓到 1ms 以內(nèi)我能接受，但是能把棧這種數(shù)據(jù)結(jié)構(gòu)的方案優(yōu)化到 2ms 以內(nèi)，這個我是真的服。
?
