网站开发员名称是什么,网站服务器管理系统,cms仿站,电商网站运营方案有效的括号 题目思路及实现方式一#xff1a;栈#xff08;推荐#xff09;思路代码实现Java版本C版本(由于C语言需要自己实现栈较为繁琐#xff0c;此处使用C)Python3版本 复杂度分析 方式二#xff1a;递归法思路代码实现Java版本C语言版本Python3版本 复杂度分析 总结相… 有效的括号 题目思路及实现方式一栈推荐思路代码实现Java版本C版本(由于C语言需要自己实现栈较为繁琐此处使用C)Python3版本 复杂度分析 方式二递归法思路代码实现Java版本C语言版本Python3版本 复杂度分析 总结相似题目 标签栈|递归
题目 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 示例 1输入s () 输出true
示例 2输入s ()[]{} 输出true 示例 3输入s (] 输出false 提示1 s.length 104 s 仅由括号 ()[]{} 组成原题LeetCode 20 有效的括号
思路及实现
方式一栈推荐
思路
判断括号的有效性可以使用「栈」这一数据结构来解决。
代码实现
Java版本
import java.util.Stack;// leetcode submit region begin(Prohibit modification and deletion)
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack(); // 创建一个栈用于存储左括号字符for (int i 0; i s.length(); i) {char c s.charAt(i);if (c ( || c [ || c {) {stack.push(c); // 如果是左括号字符将其压入栈中} else {if (stack.isEmpty()) {return false; // 如果栈为空说明缺少左括号返回false}char top stack.pop(); // 弹出栈顶元素if (c ) top ! () {return false; // 如果当前字符是右括号且与栈顶元素不匹配返回false}if (c ] top ! [) {return false;}if (c } top ! {) {return false;}}}return stack.isEmpty(); // 最后判断栈是否为空如果为空说明每个左括号都有匹配的右括号则返回true否则返回false}
}
// leetcode submit region end(Prohibit modification and deletion) 说明 使用栈来判断给定的字符串中的括号是否匹配。先创建一个空栈然后遍历字符串中的每个字符。如果是左括号字符则压入栈中如果是右括号字符则与栈顶元素进行匹配。匹配成功则继续遍历匹配失败则返回false。最后判断栈是否为空如果为空则说明所有的括号都被匹配返回true否则说明还有未匹配的括号返回false C版本(由于C语言需要自己实现栈较为繁琐此处使用C)
#include iostream
#include stack
#include stringusing namespace std;bool isValid(string s) {stackchar stk; // 创建一个栈用于存储左括号字符for (char c : s) {if (c ( || c [ || c {) {stk.push(c); // 如果是左括号字符将其压入栈中} else {if (stk.empty()) {return false; // 如果栈为空说明缺少左括号返回false}char top stk.top(); /* 获取栈顶元素 */stk.pop(); // 弹出栈顶元素if (c ) top ! () {return false; // 如果当前字符是右括号且与栈顶元素不匹配返回false}if (c ] top ! [) {return false;}if (c } top ! {) {return false;}}}return stk.empty(); // 最后判断栈是否为空如果为空说明每个左括号都有匹配的右括号则返回true否则返回false
}说明 使用C的标准库来实现栈判断给定的字符串中的括号是否匹配。首先创建一个stack用于存储左括号字符。然后遍历字符串中的每个字符如果是左括号字符则将其压入栈中如果是右括号字符则与栈顶元素进行匹配。匹配成功则继续遍历匹配失败则返回false。最后判断栈是否为空如果为空则说明所有的括号都被匹配返回true否则说明还有未匹配的括号返回false。 Python3版本
class Solution:def isValid(self, s: str) - bool:stack [] # 创建一个栈用于存储左括号字符brackets {(: ), [: ], {: }}for char in s:if char in brackets.keys(): # 如果是左括号字符将其压入栈中stack.append(char)elif char in brackets.values(): # 如果是右括号字符if not stack: # 如果栈为空说明缺少左括号返回Falsereturn Falsetop stack.pop() # 弹出栈顶元素if char ! brackets[top]: # 如果当前字符与栈顶元素不匹配返回Falsereturn Falsereturn len(stack) 0 # 判断栈是否为空为空说明每个左括号都有匹配的右括号说明 创建一个列表作为栈来判断给定的字符串中的括号是否匹配。首先定义了一个字典brackets用来存储左括号和右括号的对应关系。然后遍历字符串中的每个字符如果是左括号字符则将其压入栈中如果是右括号字符则和栈顶元素进行匹配。匹配成功则继续遍历匹配失败则返回False。最后判断栈是否为空如果为空则说明所有的括号都被匹配返回True否则说明还有未匹配的括号返回False 复杂度分析
时间复杂度O(n)其中 n 是字符串 s 的长度。空间复杂度O(n)其中n为字符串的长度。在最坏情况下所有的字符都是左括号需要将其全部入栈占用了O(n) 的空间。
方式二递归法
思路
递归法解决括号有效性问题的思路是从字符串的起始位置开始不断地递归判断子字符串的有效性
代码实现
Java版本
public class Solution {public boolean isValid(String s) {// 调用递归辅助函数进行判断return isValidHelper(s, 0, s.length() - 1);}private boolean isValidHelper(String s, int start, int end) {// base case: 当起始位置等于结束位置时返回该位置字符是否为左括号或右括号if (start end) {return s.charAt(start) ( || s.charAt(start) ) ||s.charAt(start) [ || s.charAt(start) ] ||s.charAt(start) { || s.charAt(start) };}// 判断字符串两侧是否匹配以及去掉最外侧字符后的子字符串是否有效if (s.charAt(start) () {if (s.charAt(end) ! )) {return false;}} else if (s.charAt(start) [) {if (s.charAt(end) ! ]) {return false;}} else if (s.charAt(start) {) {if (s.charAt(end) ! }) {return false;}} else {// 如果初始字符不是左括号直接递归调用处理去掉首位字符的子字符串return isValidHelper(s, start 1, end - 1);}// 递归判断去掉左右括号后的子字符串是否有效return isValidHelper(s, start 1, end - 1);}
} 说明 isValidHelper 方法作为递归辅助函数用于实现递归逻辑。isValid 方法则是调用递归辅助函数并返回结果 C语言版本
#include stdbool.h // 包含 bool 类型定义的头文件bool isValidHelper(char* s, int start, int end) {// base case: 当起始位置等于结束位置时返回该位置字符是否为左括号或右括号if (start end) {return s[start] ( || s[start] ) ||s[start] [ || s[start] ] ||s[start] { || s[start] };}// 判断字符串两侧是否匹配以及去掉最外侧字符后的子字符串是否有效if (s[start] () {if (s[end] ! )) {return false;}} else if (s[start] [) {if (s[end] ! ]) {return false;}} else if (s[start] {) {if (s[end] ! }) {return false;}} else {// 如果初始字符不是左括号直接递归调用处理去掉首位字符的子字符串return isValidHelper(s, start 1, end - 1);}// 递归判断去掉左右括号后的子字符串是否有效return isValidHelper(s, start 1, end - 1);
}bool isValid(char* s) {// 调用递归辅助函数进行判断return isValidHelper(s, 0, strlen(s) - 1);
} 说明 通过递归方式来判断给定的字符串 “s” 是否有效。isValidHelper 函数作为递归辅助函数用于实现递归逻辑。isValid 函数则是调用递归辅助函数并返回结果。需要注意的是在C语言中需要引入 stdbool.h 头文件来使用 bool 类型 Python3版本
def isValid(s: str) - bool:def isValidHelper(s: str, start: int, end: int) - bool:# Base case: 当起始位置等于结束位置时返回该位置字符是否为左括号或右括号if start end:return s[start] ( or s[start] ) or s[start] [ or s[start] ] or s[start] { or s[start] }# 判断字符串两侧是否匹配以及去掉最外侧字符后的子字符串是否有效if s[start] (:if s[end] ! ):return Falseelif s[start] [:if s[end] ! ]:return Falseelif s[start] {:if s[end] ! }:return Falseelse:return isValidHelper(s, start 1, end - 1)# 递归判断去掉左右括号后的子字符串是否有效return isValidHelper(s, start 1, end - 1)return isValidHelper(s, 0, len(s) - 1) 说明 通过递归方式判断给定字符串 “s” 是否有效。如果有效返回 True如果无效返回 False 复杂度分析
假设输入字符串的长度为 n。
时间复杂度 O(n) 在最坏情况下需要递归访问字符串的每个字符即递归的深度为字符串的长度 n。每次递归操作的时间复杂度为 O(1)。 因此递归法的时间复杂度为 O(n)。空间复杂度 O(n) 在递归的过程中除了原始的字符串外没有使用额外的空间。递归调用的栈空间的最大深度为 n/2平均情况下为 n/4即最多有 n/2 个递归调用帧。 因此递归法的空间复杂度为 O(n)。
总结
对比点递归法栈解法思路直观性直观相对复杂递归深度问题可能存在递归深度过大导致栈溢出的风险无递归深度限制利用系统调用栈是否时间复杂度O(n)O(n)空间复杂度O(n)O(n)实现复杂性相对简单相对复杂额外空间需求无有
相似题目
题目链接难度有效的括号LeetCode-20简单最长有效括号LeetCode-32困难删除无效的括号LeetCode-301困难有效的括号字符串LeetCode-678中等括号的分数LeetCode-856中等
