題目: LeetCode - 20. Valid Parentheses
題目說明
給一個只含有括號的字串,求此字串是否合法。字串合法須滿足以下條件:
- 開括號必須用相同類型的括號封閉
- 開括號必須以正確的順序關閉
解題思路
由於閉括號必須搭配相同類型的開括號,所以可以使用 Stack,碰到開括號時直接推入,若碰到閉括號時只要看 stack.top()
是否是對應的開括號即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| class Solution { public: bool isValid(string s) { stack<char> s_; for(auto i : s) if(i == '(' || i == '{' || i == '[') s_.push(i); else if(!s_.empty()) switch(i) { case ')': if(s_.top() != '(') return false; s_.pop(); break; case '}': if(s_.top() != '{') return false; s_.pop(); break; case ']': if(s_.top() != '[') return false; s_.pop(); break; } else return false; return s_.empty(); } };
|