LeetCode#20 Valid Parentheses

分析

原題連結

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

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

Source 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 25 26 27 28 29 30 31 32 33

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