0020-有效的括号

题目链接

题目描述

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

示例

示例1：

输入：s = “()[]{}” 输出：true

提示

• 1 <= s.length <= 10

• s 仅由括号 '()[]{}' 组成

  思路

  栈

  有三种不匹配的情况：

• 左括号数量多于右括号：当字符串遍历结束后，栈不为空。

• 右括号数量多于左括号：当字符串遍历过程中，栈已经空了。
• 左右括号不匹配：当字符串遍历过程中左右括号不匹配。

  题解

  ```cpp const unordered_map mapping = { {‘)’, ‘(‘}, {‘]’, ‘[‘}, {‘}’, ‘{‘}};

class Solution { public: bool isValid(string s) { int size = s.size(); if (size % 2) { return false; } stack stk; for (char c : s) { if (mapping.count(c)) { if (stk.empty() || stk.top() != mapping.at(c)) { return false; } stk.pop(); } else { stk.push(c); } }

    return stk.empty();
}

}; ```

复杂度分析

• 时间复杂度：
• 空间复杂度：，其中 为字符集大小，这里为6.