LeetCode20_有效的括号

标签：#栈 #字符串

Ⅰ. 题目

• 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

• 有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 每个右括号都有一个对应的相同类型的左括号。

Ⅱ. 示例

· 示例 1：
输入：s = “()”
输出：true

· 示例 2：
输入：s = “()[]{}”
输出：true

· 示例 3：
输入：s = “(]”
输出：false

· 示例 4：
输入：s = “([])”
输出：true

0.个人方法

这是一道栈的经典匹配问题。直接遍历字符串s：遇到左括号就入栈；遇到右括号就和栈顶的左括号看看是否匹配，不匹配的话直接false，匹配的话就继续遍历，直到所有括号处理完毕。如果最后栈不为空，说明有多余的左括号没有被配对，这也是不可以的，也返回false。

class Solution {
public:bool isValid(string s) {std::stack<char> SStack;std::unordered_map<char, char> bracket_map = {{')', '('}, {'}', '{'}, {']', '['}};for (char ch : s){if (ch == '(' || ch == '{' || ch == '['){SStack.push(ch);}else if (ch == ')' || ch == '}' || ch == ']'){if (SStack.empty() || SStack.top() != bracket_map[ch]){return false;}else{SStack.pop();   // 弹出栈顶元素}}}return SStack.empty();}
};

• 复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。

  • 空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。