LeetCode 20. Valid Parentheses [Easy] [C++] 解題筆記

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

EX:

        Input: "()[]{}"

       Output: true

        Input: "([)]"

       Output: false

想法:

        驗證括弧最直覺常用的方式就是 stack 拉，我們可以用一個 stack 紀錄出現過得左括弧，如果遇到

右括弧且 stack.top 的左括弧可以與之匹配的話就 pop，反之就是 invalid，而若 stack 為空且出現右括弧

或是遍歷完之後 stack 中還有左括弧也都是 invalid。

Complexity: O(n) time, O(n) space.

完整程式碼:

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