【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;      }  };