木又同学2020年第14篇解题报告
leetcode第20题:有效的括号
https://leetcode-cn.com/problems/valid-parentheses/
【题目】
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
【思路】
开心~又一次写完代码,一跑,全部通过
本题是栈的典型应用。遍历字符串,如果遇到'{'、'['、'}'这三个字符,则压栈;否则,判断栈是否为空,同时字符与栈顶元素是否对应,若任何一个条件不满足,则返回False。循环结束后,判断栈是否为空,如为空,则返回True。
【代码】
python版本
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
# 奇数个,肯定不行
if len(s) % 2 != 0:
return False
# 空字符串,返回True
if s == '':
return True
d = {')': '(', ']': '[', '}': '{'}
# 使用栈来存储
stack = []
for si in s:
# 压栈
if si in '([{':
stack.append(si)
# 弹栈
else:
if len(stack) == 0 or d[si] != stack[-1]:
return False
stack.pop()
return len(stack) == 0
C++版本
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0)
return false;
stack<char> res;
bool flag = true;
for (auto si: s) {
if (si == '(' || si == '[' || si == '{') {
res.push(si);
} else {
// 栈是否为空
if (res.size() == 0) {
flag = false;
break;
}
// 元素是否对应
if ((res.top() == '(' && si == ')') || (res.top() == '[' && si == ']') || (res.top() == '{' && si == '}')) {
res.pop();
} else {
flag = false;
break;
}
}
}
return flag && res.size() == 0;
}
};