20. Valid Parentheses (E)
https://leetcode.com/problems/valid-parentheses/
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.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
s
consists of parentheses only'()[]{}'
.
Solution:
解决这个问题之前,我们先降低难度,思考一下,如果只有一种括号 ()
,应该如何判断字符串组成的括号是否合法呢?
假设字符串中只有圆括号,如果想让括号字符串合法,那么必须做到:
每个右括号 )
的左边必须有一个左括号 (
和它匹配。
比如说字符串 ()))((
中,中间的两个右括号左边就没有左括号匹配,所以这个括号组合是不合法的。
那么根据这个思路,我们可以写出算法:
bool isValid(string str) {
// 待匹配的左括号数量
int left = 0;
for (int i = 0; i < str.size(); i++) {
if (s[i] == '(') {
left++;
} else {
// 遇到右括号
left--;
}
// 右括号太多
if (left == -1)
return false;
}
// 是否所有的左括号都被匹配了
return left == 0;
}
如果只有圆括号,这样就能正确判断合法性。对于三种括号的情况,我一开始想模仿这个思路,定义三个变量 left1
,left2
,left3
分别处理每种括号,虽然要多写不少 if else 分支,但是似乎可以解决问题。
但实际上直接照搬这种思路是不行的,比如说只有一个括号的情况下 (())
是合法的,但是多种括号的情况下, [(])
显然是不合法的。
仅仅记录每种左括号出现的次数已经不能做出正确判断了,我们要加大存储的信息量,可以利用栈来模仿类似的思路。栈是一种先进后出的数据结构,处理括号问题的时候尤其有用。
我们这道题就用一个名为 left
的栈代替之前思路中的 left
变量,遇到左括号就入栈,遇到右括号就去栈中寻找最近的左括号,看是否匹配:
bool isValid(string str) {
stack<char> left;
for (char c : str) {
if (c == '(' || c == '{' || c == '[')
left.push(c);
else { // 字符 c 是右括号
if (!left.empty() && leftOf(c) == left.top())
left.pop();
else
// 和最近的左括号不匹配
return false;
}
}
// 是否所有的左括号都被匹配了
return left.empty();
}
char leftOf(char c) {
if (c == '}') return '{';
if (c == ')') return '(';
return '[';
}
Last updated
Was this helpful?