LeetCode 0020 - Valid Parentheses
# Hints
- 水题 + 栈
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
# 题意
给定一个长为 的字符串,仅由 '('
, ')'
, '{'
, '}'
, '['
, ']'
六种字符组成,判断该串是否为一个合法的括号匹配。
# 题解
括号匹配是栈的一个基本应用。
我们直接遍历整个字符串,遇到左括号则入栈,遇到右括号则判断与栈顶的左括号是否匹配,如果匹配则出栈,否则不合法。
# AC代码
class Solution {
public:
bool isValid(string str) {
stack<char> s;
for (auto ch : str) {
if (ch == '(' || ch =='{' || ch == '[') {
s.push(ch);
} else if (!s.empty() && isPair(s.top(), ch)) {
s.pop();
} else {
return false;
}
}
return s.empty();
}
// 判断是否配对
inline bool isPair(char l, char r) {
return ((l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']'));
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01