本文是圖解 LeetCode 系列文章之一。

個人網站：https://www.cxyxiaowu.com

題目來源於 LeetCode 上第 20 號問題：有效的括號。題目難度為 Easy，目前通過率為 37.8% 。

題目描述

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

有效字符串需滿足：

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。

注意空字符串可被認為是有效字符串。

示例 1:

輸入: "()"
輸出: true

示例 2:

輸入: "()[]{}"
輸出: true

示例 3:

輸入: "(]"
輸出: false

示例 4:

輸入: "([)]"
輸出: false

示例 5:

輸入: "{[]}"
輸出: true

題目解析

這道題讓我們驗證輸入的字符串是否為括號字符串，包括大括號，中括號和小括號。

這裡我們使用棧。

• 遍歷輸入字符串
• 如果當前字符為左半邊括號時，則將其壓入棧中
• 如果遇到右半邊括號時，分類討論：
• 1）如棧不為空且為對應的左半邊括號，則取出棧頂元素，繼續循環
• 2）若此時棧為空，則直接返回false
• 3）若不為對應的左半邊括號，反之返回false

動畫描述

代碼實現

class Solution {
public:
 bool isValid(string s) {
 stack<char> stack;
 for( int i = 0 ; i < s.size() ; i ++ )
 if( s[i] == '(' || s[i] == '{' || s[i] == '[')
 stack.push(s[i]);
 else{
 if( stack.size() == 0 )
 return false;
 char c = stack.top();
 stack.pop();
 char match;
 if( s[i] == ')' ){
 match = '(';
 }
 else if( s[i] == ']' ){
 match = '[';
 }
 else{
 match = '{';
 }
 if(c != match) return false;
 }
 if( stack.size() != 0 )
 return false;
 return true;
 }
};
/<char>

閱讀更多 五分鐘學算法 的文章

關鍵字: match 有效 示例