本文是圖解 LeetCode 系列文章之一。
個人網站:https://www.cxyxiaowu.com
題目來源於 LeetCode 上第 20 號問題:有效的括號。題目難度為 Easy,目前通過率為 37.8% 。
題目描述
給定一個只包括 '(',')','{','}','[',']' 的字符串,判斷字符串是否有效。
有效字符串需滿足:
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。
示例 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>
閱讀更多 五分鐘學算法 的文章