# 引言
题目链接：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) | |
} |
