[教學] Leetcode-Valid Parentheses－一個小小工程師的心情抒發天地

剛剛看了一下累積人數, 突然覺得還蠻自豪的, 寫了這麼多年, 終於升級成百萬部落客了, 這感覺挺妙的; 不知道這樣會不會有人想要來打點廣告之類的:D ( 有的話歡迎底下留言或私訊一下好了, 讓我也享受一下接接業配的感覺 ).

今天一樣寫點東西, 通常寫這個都不用很久, 反而是在優化上面, 會需要花比較多時間, 嘖嘖.

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

An input string is valid if:

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

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

今天因為真的很忙, 一堆事情要處理, 加上下午還要開會, 所以就沒有考慮什麼效率問題 ( 不過話雖如此, 這個暴力破解法速度也是很快的好嗎 XD , 至少贏過上面58%的人 ), 為了避免沒圖沒真相, 貼一下.

#include <stack>
bool isValid(string s) {

   stack<char>_stack;
   for (int i = 0; i < s.size(); i++)
   {
       if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
           _stack.push(s[i]);
       }
       else
       if (!_stack.empty() && s[i] == ')')
       {
           if (_stack.top() == '(')
           {
               _stack.pop();
           }
           else
               return false;
       }
       else
       if (!_stack.empty() && s[i] == '}')
       {
           if (_stack.top() == '{')
           {
               _stack.pop();
           }
           else
               return false;
       }
       else
       if (!_stack.empty() && s[i] == ']')
       {
           if (_stack.top() == '[')
           {
               _stack.pop();
           }
           else
               return false;
       }
       else if (_stack.empty() == true && s[i] == ']' || s[i] == '}' || s[i] == ')')
       {
           return false;
       }
   }
   if (_stack.empty() == true)
       return true;
   else
       return false;
}