引言
题目链接：https://leetcode.com/problems/valid-parentheses/description/
题目大意
输入一个由各种括号组成的字符串，按照如下规则判断字符串是否有效
条件:
- 开括号必须由相同类型的括号来关闭，即'('由')'关闭、'['由']'关闭，'{'由'}'关闭.
- 按照正确的顺序打开的括号必须按照同样顺序关闭。
Hont: Note that an empty string is also considered valid.
- Example
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Input: "()" Output: true Input: "()[]{}" Output: true Input: "(]" Output: false Input: "([)]" Output: false Input: "{[]}" Output: true |
题解
一句话题解：括号匹配的规则符合后进先出的原则，直接使用stack模拟流程即可。每次选取栈顶和当前输入比较，看是否匹配；匹配则栈顶元素出栈，否则当前元素入栈，当输入串遍历完毕后判断栈是否为空即可
复杂度
时间复杂度 O(n)
空间复杂度 O(n)
AC代码
c++版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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版本
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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) } |
