給定一個(gè)只包括 '('儿惫，')'澡罚，'{'，'}'肾请，'['留搔，']' 的字符串 s ，判斷字符串是否有效铛铁。
有效字符串需滿足：
- 左括號(hào)必須用相同類型的右括號(hào)閉合隔显。
- 左括號(hào)必須以正確的順序閉合。
https://leetcode-cn.com/problems/valid-parentheses
示例1：
輸入：s = "()"
輸出：true
示例2：
輸入：s = "()[]{}"
輸出：true
示例3：
輸入：s = "(]"
輸出：false
示例4：
輸入：s = "([)]"
輸出：false
示例 5：
輸入：s = "{[]}"
輸出：true
提示：
1 <= s.length <= 104
s 僅由括號(hào) '()[]{}' 組成
Java解法
思路：
- 做過(guò)的題饵逐，印象比較深的解法是括眠，輸入左括號(hào)，對(duì)棧放入正確的右括號(hào)倍权，輸入右括號(hào)掷豺，棧彈出對(duì)應(yīng)比較是否正確匹配，輸入完成账锹，棧為空則正確
- 老的解法做了各種switch萌业，比較麻煩
package sj.shimmer.algorithm;
import java.util.Stack;
/**
* Created by SJ on 2021/2/6.
*/
class D13 {
public static void main(String[] args) {
System.out.println(isValid("()"));
System.out.println(isValid("()[]{}"));
System.out.println(isValid("(]"));
System.out.println(isValid("([)]"));
System.out.println(isValid("{[]}"));
}
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '(':
stack.push(')');
break;
case '{':
stack.push('}');
break;
case '[':
stack.push(']');
break;
case ')':
case '}':
case ']':
if (stack.isEmpty()||s.charAt(i)!=stack.pop()) {
return false;
}
break;
default:
return false;
}
}
return stack.isEmpty();
}
}
官方解
-
棧
官方解... Emmm優(yōu)雅
我們遍歷給定的字符串 s。當(dāng)我們遇到一個(gè)左括號(hào)時(shí)奸柬，我們會(huì)期望在后續(xù)的遍歷中生年，有一個(gè)相同類型的右括號(hào)將其閉合。由于后遇到的左括號(hào)要先閉合廓奕，因此我們可以將這個(gè)左括號(hào)放入棧頂抱婉。
當(dāng)我們遇到一個(gè)右括號(hào)時(shí)，我們需要將一個(gè)相同類型的左括號(hào)閉合桌粉。此時(shí)蒸绩，我們可以取出棧頂?shù)淖罄ㄌ?hào)并判斷它們是否是相同類型的括號(hào)。如果不是相同的類型铃肯，或者棧中并沒(méi)有左括號(hào)患亿，那么字符串 s 無(wú)效，返回 False押逼。為了快速判斷括號(hào)的類型步藕，我們可以使用哈希表存儲(chǔ)每一種括號(hào)。哈希表的鍵為右括號(hào)挑格，值為相同類型的左括號(hào)咙冗。
在遍歷結(jié)束后，如果棧中沒(méi)有左括號(hào)漂彤，說(shuō)明我們將字符串 s 中的所有左括號(hào)閉合雾消，返回 True灾搏，否則返回 False。
注意到有效字符串的長(zhǎng)度一定為偶數(shù)立润，因此如果字符串的長(zhǎng)度為奇數(shù)狂窑，我們可以直接返回 False，省去后續(xù)的遍歷判斷過(guò)程
class Solution { public boolean isValid(String s) { int n = s.length(); if (n % 2 == 1) { return false; } Map<Character, Character> pairs = new HashMap<Character, Character>() {{ put(')', '('); put(']', '['); put('}', '{'); }}; Deque<Character> stack = new LinkedList<Character>(); for (int i = 0; i < n; i++) { char ch = s.charAt(i); if (pairs.containsKey(ch)) { if (stack.isEmpty() || stack.peek() != pairs.get(ch)) { return false; } stack.pop(); } else { stack.push(ch); } } return stack.isEmpty(); } }時(shí)間復(fù)雜度：O(n)范删，其中 n 是字符串 s 的長(zhǎng)度蕾域。
空間復(fù)雜度：O(n+∣Σ∣)，其中 Σ 表示字符集到旦，本題中字符串只包含 6 種括號(hào)旨巷，∣Σ∣=6。棧中的字符數(shù)量為 O(n)添忘，而哈希表使用的空間為O(∣Σ∣)采呐，相加即可得到總空間復(fù)雜度
