# 引言
题目链接：https://leetcode.com/problems/valid-parentheses/description/
# 题目大意
输入一个由各种括号组成的字符串, 按照如下规则判断字符串是否有效
条件:
- 开括号必须由相同类型的括号来关闭, 即'('由')'关闭、'['由']'关闭, '{'由'}'关闭.
- 按照正确的顺序打开的括号必须按照同样顺序关闭。
Hont: Note that an empty string is also considered valid.
- Example
Input: "()"
Output: true
Input: "()[]{}"
Output: true
Input: "(]"
Output: false
Input: "([)]"
Output: false
Input: "{[]}"
Output: true# 题解
# 一句话题解
括号匹配的规则符合后进先出的原则, 直接使用stack模拟流程即可。每次选取栈顶和当前输入比较, 看是否匹配；匹配则栈顶元素出栈, 否则当前元素入栈, 当输入串遍历完毕后判断栈是否为空即可
# 复杂度
时间复杂度 O(n)
空间复杂度 O(n)
# AC代码
c++版本
class Solution
{
public:
bool isValid(string s)
{
stack<char> match;
for (const char c : s)
{
if (isMatch(match.empty() ? '\0' : match.top(), c))
{
match.pop();
}
else
{
match.push(c);
}
}
return match.empty();
}
private:
bool isMatch(const char a, const char b)
{
if ((a == '(' && b == ')') ||
(a == '[' && b == ']') || (a == '{' && b == '}'))
{
return true;
}
return false;
}
};go版本
func isMatch(a, b byte) bool {
if (a == '(' && b == ')') ||
(a == '[' && b == ']') || (a == '{' && b == '}') {
return true
}
return false
}
func isValid(s string) bool {
var match []byte
for _, c := range s {
lens := len(match)
if 0 == lens || !isMatch(match[lens-1], byte(c)) {
match = append(match, byte(c))
} else {
match = match[0 : lens-1]
}
}
return 0 == len(match)
}
有什么想法，欢迎留下评论。