题目描述
Given a string
s
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.
例子
例子 1
Input:
s = "()"
Output:true
例子 2
Input:
s = "()[]{}"
Output:true
例子 3
Input:
s = "(]"
Output:false
例子 4
Input:
s = "([)]"
Output:false
例子 5
Input:
s = "{[]}"
Output:true
Follow Up
Note
Constraints
1 <= s.length <= 10^4
s
consists of parentheses only'()[]{}'
.
解题思路
这道题可以用栈来解。首先建立一个哈希表记录左右括号之间的对应的关系。然后从头遍历字符串,遇到左括号压入栈中,遇到右括号时有三种情况:
- 栈为空,表示当前左边没有左括号,或者所有左括号都匹配了,所以返回
false
- 栈顶为对应的左括号,此时可以用于匹配当前右括号。将其弹出,继续遍历
- 栈顶为不对应的左括号,表示最近的没匹配的左括号不能匹配,类似于
[)
返回false
除此之外在最开始可以做个长度判断,如果是奇数可以直接返回 false
,代码如下:
#include <string>
#include <stack>
#include <unordered_map>
class Solution {
public:
bool isValid(std::string s) {
if (s.length() % 2 == 1) return false;
std::stack<char> stk;
std::unordered_map<char, char> pairs ({
{'(', ')'},
{'[', ']'},
{'{', '}'}
});
for (int i = 0; i < s.length(); i++) {
if (pairs.count(s[i])) {
stk.push(s[i]);
} else {
if (stk.empty() || s[i] != pairs[stk.top()]) return false;
stk.pop();
}
}
return stk.empty();
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(n)
GitHub 代码同步地址: 20.ValidParentheses.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions