目錄

題目

思路?

注意

---

題目

給定一個只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。
3. 每個右括號都有一個對應的相同類型的左括號。

示例 1：

輸入：s = "()"
輸出：true

示例?2：

輸入：s = "()[]{}"
輸出：true

示例?3：

輸入：s = "(]"
輸出：false

提示：

• 1 <= s.length <= 104
• s?僅由括號?'()[]{}'?組成

思路?

不匹配的情況：

1. 第一種情況，字符串里左方向的括號多余了 ，所以不匹配。 比如：（ [ { } ]? ( )

? ? ?已經遍歷完了字符串，但是棧不為空，說明有相應的左括號沒有右括號來匹配，所以return false

? ? ?2.第二種情況，括號沒有多余，但是 括號的類型沒有匹配上。 比如 （ [ { } } ）

? ? ? 遍歷字符串匹配的過程中，發現棧里沒有要匹配的字符。所以return false

? ? ?3.第三種情況，字符串里右方向的括號多余了，所以不匹配。比如：{（[ ]）} ) )

? ? ?遍歷字符串匹配的過程中，棧已經為空了，沒有匹配的字符了，說明右括號沒有找到對應的左括號return false

代碼

class Solution {public boolean isValid(String s) {
Deque<Character> stack = new LinkedList<>();//定義一個棧
for(int i=0;i<s.length();i++){//遍歷schar c=s.charAt(i);if (c=='('){//這里的思路是只要有左邊的要想匹配就得有右括號，所以我遍歷考慮左括號，把右邊的放入棧中，到時候匹配，如果成功則出棧，若沒有則返回falsestack.push(')');}else if (c=='['){stack.push(']');}else if (c=='{'){stack.push('}');}else{if(!stack.isEmpty() && c==stack.peek()){//前面的條件是如果這個括號是)(的話，沒有這個條件就會判斷錯誤。因為第一個是），就會直接來到這個else，但是此時棧還是空的，會得到null，但是他還要和前面基本類型的char作比較，所以他會嘗試把null轉換為基本類型的char，無法按轉換就會拋出空指針異常stack.pop();}else{return false;}}
}
return stack.isEmpty(); //最后遍歷完如果棧還不為空，那么就不匹配。}}

class Solution {public boolean isValid(String s) {Deque<Character> deque = new LinkedList<>();char ch;for (int i = 0; i < s.length(); i++) {ch = s.charAt(i);//碰到左括號，就把相應的右括號入棧if (ch == '(') {deque.push(')');}else if (ch == '{') {deque.push('}');}else if (ch == '[') {deque.push(']');} else if (deque.isEmpty() || deque.peek() != ch) {//這里用或而不是和是因為如果這個是空棧，和的情況還要取出空棧的棧頂元素，會報錯，所以二者順序不能改變且必須用和return false;}else {//如果是右括號判斷是否和棧頂元素匹配deque.pop();}}//最后判斷棧中元素是否匹配return deque.isEmpty();}
}

注意

在寫c=='('的時候我們用的是單引號，如果用雙引號就會報錯

1. 雙引號（" "）：

• 雙引號用于表示字符串（String），是一個字符序列。
• 字符串是不可變的，一旦創建后，其內容不能被修改。
• 用雙引號括起來的內容可以包含任意字符，包括字母、數字、符號、空格等

? ? ?2.單引號（’ '）：

• 單引號用于表示字符（char），是一個單個字符。
• 字符是基本數據類型，表示一個Unicode字符，只能包含一個字符。
• 用單引號括起來的內容只能是單個字符，例如字母、數字、符號，但不能是字符串。

?而在這個代碼中我們定義的c屬于char類型，所以只能用單引號

還有一個簡化操作：要想括號匹配，那么她一定是偶數個，所以可以如果是奇數，可以直接返回false，簡化代碼