LeetCode 20. 有效的括号(Valid Parentheses)
程序员文章站
2022-05-20 13:19:02
...
栈思想
关于有效括号表达式的一个有趣属性是有效表达式的子表达式也应该是有效表达式。
整个表达式是有效的,而它的子表达式本身也是有效的。这为问题提供了一种递归结构。(栈思想)
从整体表达式中一次删除一个较小的表达式,因为这是一个有效的表达式,我们最后剩留下一个空字符串。
class Solution {
public:
bool isValid(string s) {
int pos = 0;
while (pos < s.length()){
//左括号,压栈
if (s[pos] == '(' || s[pos] == '{' || s[pos] == '[') {
pos++;
continue;
}
//括号匹配,出栈
if((s[pos] == ')' && s[pos-1] == '(') || (s[pos] == ']' && s[pos-1] == '[') || (s[pos] == '}' && s[pos-1] == '{'))
{
s.erase(pos-1, 2);
pos--;
}
else
return false;
}
if (s.length() == 0)
return true;
else
return false;
}
};
上一篇: LeetCode - 112. 路径总和
下一篇: 问题 F: DS堆栈--迷宫求解