LeetCodeDay33 —— 有效的括号☆

20. 有效的括号

描述

• 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
• 有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 注意空字符串可被认为是有效字符串。

示例

示例 1:
  输入: "()"
  输出: true

示例 2:
  输入: "()[]{}"
  输出: true

示例 3:
  输入: "(]"
  输出: false

示例 4:
  输入: "([)]"
  输出: false

示例 5:
  输入: "{[]}"
  输出: true

思路

1. 基本的括号匹配算法，利用栈实现，左括号入栈、右括号与栈顶元素匹配。
2. 小技巧，可以预先存放1个元素到栈内，如'#'，后续就不用判空了。

class Solution {
 public:
  bool isValid(string s) {
    stack<char> ms;
    for (char ch : s) {
      if (ch == '(' || ch == '{' || ch == '[')
        ms.push(ch);
      else if (ch == ')') {
        if (ms.empty() || ms.top() != '(') return false;
        ms.pop();
      } else if (ch == '}') {
        if (ms.empty() || ms.top() != '{') return false;
        ms.pop();
      } else if (ch == ']') {
        if (ms.empty() || ms.top() != '[') return false;
        ms.pop();
      }
    }
    return ms.empty();
  }
};