对括号的合法性判断是一个很常见且实用的问题,比如说我们写的代码,编辑器和编译器都会检查括号是否正确闭合。而且我们的代码可能会包含三种括号{},判断起来有一点难度。
本文就来聊一道关于括号合法性判断的算法题,相信能加深你对栈这种数据结构的理解。
题目很简单,输入一个字符串,其中包含{}六种括号,请你判断这个字符串组成的括号是否合法。
Input: "()[]{}"
Output: true
Input: "([)]"
Output: false
Input: "{[]}"
Output: true
解决这个问题之前,我们先降低难度,思考一下,如果只有一种括号(),应该如何判断字符串组成的括号是否合法呢?
一、处理一种括号
字符串中只有圆括号,如果想让括号字符串合法,那么必须做到:
每个右括号)的左边必须有一个左括号(和它匹配。
比如说字符串()))((中,索引为 2 和 3 的两个右括号左边就没有左括号匹配,所以这个括号组合是不合法的。
所以我们可以一边遍历一边记录遇到左括号的个数,每次遇到右括号就匹配一个左括号数。根据这个思路,我们可以写出算法:
bool isValid(string str) {
// 待匹配的左括号数量
int left = 0;
for (char c : str) {
if (c == '(')
left++;
else // 遇到右括号
left--;
if (left < 0)
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 '[';
}
以上就是判断括号合法性的算法思路,核心就是利用了栈先进后出的特点,栈顶元素就是最近的左括号,遇到右括号就在栈顶判断就行了。
其实括号相关的问题都不复杂,就是会者不难,难者不会。
来源 | github
作者 | labuladong
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。