LeetCode#20 Valid Parentheses

分析

原題連結

這題早在 1989 出版的 C 名題精選百則就有了(問題6-1 括號匹配問題)，不過當時冼鏡光老師給出的範例只有小括號「( )」， LeetCode 版多出了中括號「[ ]」與大括號「{ }」(強國叫花括號)，不過解法仍然是使用 stack。

這一題小弟 10 年前不看解答第一次就做對了，這次也是一次成功。這一題很適合用來面試，如果有人連這麼簡單的題目都答錯那也太...

Source Code

class Solution {
public:
    bool isValid(string s) {
        vector<char> stack;
        stack.reserve(s.size());
        for(int i = 0; i < s.size(); ++i){
            switch(s[i]){
                case '(':
                case '[':
                case '{':
                    stack.push_back(s[i]);
                    break;
                case ')':
                    if(stack.empty() || stack.back() != '(')
                        return false;
                    stack.pop_back();
                    break;
                case ']':
                    if(stack.empty() || stack.back() != '[')
                        return false;
                    stack.pop_back();
                    break;
                case '}':
                    if(stack.empty() || stack.back() != '{')
                        return false;
                    stack.pop_back();
                    break;
            }
        }

        return (stack.empty());
    }
};