leetcode：20. 有效的括号

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

示例：

  1. 输入：s = "()"
  2. 输出：true
  1. 输入：s = "()[]{}"
  2. 输出：true
  1. 输入：s = "(]"
  2. 输出：false
  1. 输入：s = "([)]"
  2. 输出：false
  1. 输入：s = "([)]"
  2. 输出：false

解答 & 代码

  1. class Solution {
  2. private:
  3.     // 判定传入的左括号 left 和右括号 right 的类型是否匹配
  4.     bool match(char left, char right)
  5.     {
  6.         return (left == '(' && right == ')') ||
  7.                 (left == '{' && right == '}') ||
  8.                 (left == '[' && right == ']');
  9.     }
  10. public:
  11.     bool isValid(string s) {
  12.         stack<char> leftStack;    // 存放左括号的栈
  13.         // 遍历字符串 s
  14.         for(int i = 0; i < s.size(); ++i)
  15.         {
  16.              // 如果当前是左括号，则入栈
  17.              if(s[i] == '(' || s[i] == '{' || s[i] == '[')
  18.                  leftStack.push(s[i]);
  19.              // 如果当前是右括号
  20.              else
  21.              {
  22.                  // 若栈不为空且该右括号和栈顶的左括号类型匹配，则弹出栈顶（匹配后抵消掉）
  23.                  if(!leftStack.empty() && match(leftStack.top(), s[i]))
  24.                      leftStack.pop();
  25.                  // 若栈为空 or 该右括号和栈顶的左括号类型不匹配，则直接返回 false
  26.                  else
  27.                      return false;
  28.              }
  29.          }
  30.          // 如果最后栈为空，则字符串 s 是有效的，返回 true；否则还有多余的左括号，返回 false
  31.          return leftStack.empty();
  32.     }
  33. };

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 O(N)：遍历字符串 s 的每个字符
  • 空间复杂度 O(N)：存放左括号的栈 leftStack，最坏情况下字符串 s 中每个字符都是左括号，则栈最大长度 N

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 11.55% 的用户
  4. 内存消耗：6.2 MB, 在所有 C++ 提交中击败了 63.98% 的用户