20. 有效的括号
描述
- 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
- 有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
思路
- 基本的括号匹配算法，利用栈实现，左括号入栈、右括号与栈顶元素匹配。
- 小技巧，可以预先存放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();
}
};
