runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: stack

Valid Parentheses

📖 description

給定一個包含括號的字串，判斷該字串是否合法 (同種類的括號要互相配對)。

ex.
    "()"      -> 合法
    "()[]{}"  -> 合法
    "(]"      -> 不合法

🧠 solution

我們無法直接看下一個是不是配對好的字元

ex.
    "({[]})"  -> 合法

但觀察過合法字串的組合方式，就可以大致上發現規律，如果一個組成方式是合法的，則表示在 () 之間，一定也是個合法的組成方式 (包含空字串)，遇到成對的括號時就消除，如此一來就可以使用 stack 的架構來完成這個操作。

⏳ time complexity

遍歷字串，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValid(string s) {
        vector<int> st;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(' || s[i]=='{' || s[i]=='[' ){               // 左括號需要找到右括號才合法
                st.emplace_back(s[i]);
            }
            else if(st.size()!=0 && s[i]==')' && st.back()=='('){   // 如果遇到的是成對的就 pop 掉前一個左括號
                st.pop_back();
            }
            else if(st.size()!=0 && s[i]=='}' && st.back()=='{'){
                st.pop_back();
            }
            else if(st.size()!=0 && s[i]==']' && st.back()=='['){
                st.pop_back();
            }
            else{
                return false;
            }
        }
        return st.size()==0 ? true : false; // 如果 stack 內還有剩下的，表示不合法
    }
};