#LeetCode:20. Valid Parentheses

灆洢 2018-10-11 22:54:15

利用 Stack (堆疊) 去 push 左邊括弧,遇到右邊括弧就 pop 出來看能不能配對,如果能完美配對就是對的,如果不行就是錯的。

C++(0ms)

/*******************************************************/
/* LeetCode 20. Valid Parentheses                      */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/11                                 */
/*******************************************************/
#include <map>
#include <stack>

class Solution {
private:
  const map<char, char> _findLeftParenthesis = {
    {')', '('},
    {'}', '{'},
    {']', '['}
  };
public:
  bool isValid(string s) {
    stack<char> checkStack;
    for(int i = 0 ; i < s.length() ; ++i){
      auto leftParenthesis = _findLeftParenthesis.find(s[i]);
      if(leftParenthesis == _findLeftParenthesis.end()){
        checkStack.push(s[i]);
        continue;
      }

      if(checkStack.empty() || leftParenthesis->second != checkStack.top()){
        return false;
      }

      checkStack.pop();
    }
    return checkStack.empty();
  }
};

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料