给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
方法一：栈+哈希表
思路分析
- 有效括号字符串的长度，一定是偶数！
- 右括号前面，必须是相对应的左括号，才能抵消！
- 右括号前面，不是对应的左括号，那么该字符串，一定不是有效的括号！
bool isValid(string s) { if (s.size() % 2) { return false; } unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; stack<char> stk; for (char ch : s) { if (pairs.count(ch)) { if (stk.empty() || stk.top() != pairs[ch]) { return false; } stk.pop(); } else { stk.push(ch); } } return stk.empty(); }
方法二：栈
bool isValid(string s) { if (s.size() % 2) { return false; } stack<char> st; for (auto ss : s) { if (ss == '(') { st.push(')'); } else if (ss == '[') { st.push(']'); } else if (ss == '{') { st.push('}'); } else { if (st.empty() || st.top() != ss) { return false; } else { st.pop(); } } } return st.empty(); }
