来源：力扣（LeetCode）
链接: https://leetcode.cn/problems/valid-parentheses/
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
示例 4：
输入：s = "([)]" 输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
- 1 <= s.length <= 1 0 4 10^4 104
- s 仅由括号 ‘()[]{}’ 组成
- 暴力法：每次遍历一遍，如果是有相邻的两个是能够匹配的就将其替换成空字符，再接着从头开始遍历，直到最终判断这个字符串是否为空；
- 栈： 这种结构非常适合栈的数据结构，如果是左括号就入栈，如果遍历碰到右括号，就与栈顶元素进行比较，看看是否能够匹配，如果不能匹配，则返回false；如果能够匹配，栈顶元素出栈，继续遍历；直到最后判断栈是否为空栈；
python实现
class Solution:
def isValid(self, s: str) -> bool:
n = len(s)
if n & 1:
return False
count = 0
while len(s) > 1:
for i in range(len(s)-1):
if s[i] == '(' and s[i+1] == ')' or s[i] == '[' and s[i+1] == ']' or s[i] == '{' and s[i+1] == '}':
s = s[:i] + s[i+2:]
count += 1
break
if count == 0:
return False
return len(s) == 0
复杂度分析
- 时间复杂度： O ( n 3 ) O(n^3) O(n3)
- 空间复杂度： O ( 1 ) O(1) O(1)
python实现
class Solution:
def isValid(self, s: str) -> bool:
n = len(s)
if n & 1:
return False
maps = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in maps:
if not stack or stack.pop() != maps[ch]:
return False
else:
stack.append(ch)
return len(stack) == 0
c++实现
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n & 1)
return false;
unordered_map maps = {
{')', '('},
{']', '['},
{'}', '{'},
};
vector stack;
for (char ch: s) {
auto it = maps.find(ch);
if (it != maps.end()) {
if (stack.empty() || stack.back() != maps[ch])
return false;
stack.pop_back();
}
else
stack.push_back(ch);
}
return stack.empty();
}
};
复杂度分析
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
