leetcode题记 20.有效的括号

题目

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1

输入: “()”
输出: true

示例 2

输入: “()[]{}”
输出: true

示例 3

输入: “(]”
输出: false

示例 4

输入: “([)]”
输出: false

示例 5

输入: “{[]}”
输出: true

来源:力扣(LeetCode)

题解

这道题我用了递归的思想,但是深究进去和其他的结题方法的本质还是一样的,也就是栈,后进先出,后发现的先匹配。每次遇到一个新的左括号就新进一个函数压一个栈。遇到匹配的合适的右括号就出栈并返回上层一个true,如果匹配到不合适的右括号,就返回false。如果在扫描到结束的时候还没有遇到匹配的括号,就返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int length, index;
string str;
bool match() {
char _match;
bool valid = false;

// 设置对当前括号匹配的右括号
if (str[index] == '(') _match = ')';
else if (str[index] == '[') _match = ']';
else if (str[index] == '{') _match = '}';

// 索引前进一步,开始对下一个符号进行分析
index++;

while (index < length) {
if (str[index] == _match) { // 匹配成功
index++;
return true;
} else if (str[index] == '(' || str[index] == '[' || str[index] == '{') { // 匹配到左括号
if (!match()) return false;
} else
return false;
}

return false;
}
bool isValid(string s) {
index = 0;
length = s.length();
str = s;
while (index < length) {
if (!match()) return false;
}
return true;
}
};

这道题还有不用递归的栈。
不用递归的栈用起来要更简单一些(个人认为),这个情况下判断的是最后栈中是否还留有未匹配的符号,而不是检查是否匹配成功,这样的思想特别的有趣。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool isValid(string s) {
stack<char> stackk;
for (char i: s) {
if (i == '(' || i == '[' || i == '{') {
stackk.push(i);
} else {
if (stackk.empty()) return false;
if (stackk.top() + 1 == i || stackk.top() + 2 == i) {
stackk.pop();
} else {
stackk.push(i);
}
}
}
return stackk.empty();
}
};

结果

执行用时 : 4 ms, 在所有 C++ 提交中击败了83.45%的用户
内存消耗 : 8.7 MB, 在所有 C++ 提交中击败了67.22%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/07/29/leetcode-20-validBracket/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,