【leetcode刷題】20T14-有效的括弧

• 2020 年 2 月 16 日
• 筆記

木又同學2020年第14篇解題報告

leetcode第20題：有效的括弧

https://leetcode-cn.com/problems/valid-parentheses/

【題目】

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字元串，判斷字元串是否有效。

有效字元串需滿足：

左括弧必須用相同類型的右括弧閉合。 左括弧必須以正確的順序閉合。 注意空字元串可被認為是有效字元串。

示例 1:  輸入: "()"  輸出: true    示例 2:  輸入: "()[]{}"  輸出: true    示例 3:  輸入: "(]"  輸出: false    示例 4:  輸入: "([)]"  輸出: false    示例 5:  輸入: "{[]}"  輸出: true  

【思路】

開心~又一次寫完程式碼，一跑，全部通過

本題是棧的典型應用。遍歷字元串，如果遇到'{'、'['、'}'這三個字元，則壓棧；否則，判斷棧是否為空，同時字元與棧頂元素是否對應，若任何一個條件不滿足，則返回False。循環結束後，判斷棧是否為空，如為空，則返回True。

【程式碼】

python版本

class Solution(object):      def isValid(self, s):          """          :type s: str          :rtype: bool          """          # 奇數個，肯定不行          if len(s) % 2 != 0:              return False          # 空字元串，返回True          if s == '':              return True            d = {')': '(', ']': '[', '}': '{'}          # 使用棧來存儲          stack = []          for si in s:              # 壓棧              if si in '([{':                  stack.append(si)              # 彈棧              else:                  if len(stack) == 0 or d[si] != stack[-1]:                      return False                  stack.pop()          return len(stack) == 0  

C++版本

class Solution {  public:      bool isValid(string s) {          if (s.size() % 2 != 0)              return false;          stack<char> res;          bool flag = true;          for (auto si: s) {              if (si == '(' || si == '[' || si == '{') {                  res.push(si);              } else {                  // 棧是否為空                  if (res.size() == 0) {                      flag = false;                      break;                  }                  // 元素是否對應                  if ((res.top() == '(' && si == ')') || (res.top() == '[' && si == ']') || (res.top() == '{' && si == '}')) {                      res.pop();                  } else {                      flag = false;                      break;                  }              }          }          return flag && res.size() == 0;      }  };