20. Valid Parentheses

1.問題

2.想法

• 提問

• function header, parameter

• test input

• 說明想法

  • 左括號時: 放到stack中

  • 右括號時:

    • 若stack是空的或是左右無法match, 回傳false

    • pop stack

  • 最後回傳判斷stack是否為空

• 測試計算複雜度: O(n) , n是長的字串的長度

3.程式碼

class Solution {
public:
    bool isValid(string s) {
        if (s.length() == 0) {
            return true;
        }
    
        int size = s.length();
        stack<char> container;
        for (int i = 0; i < size; i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
                container.push(s[i]);
            } else {
                if (container.empty() || 
                    !isClose(container.top(), s[i])) {
                    return false;
                }
                container.pop();
            }
        }
        
        return container.empty();
    }
    
    bool isClose(char left, char right){
        if ((left == '(' && right == ')') ||
            (left == '{' && right == '}') ||
            (left == '[' && right == ']') ){
            return true;
        }
        return false;
    }
};