題目： 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();
    }
};