leetcode算法题-有效的括号(简单)

简介: 【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。

以下是关于 LeetCode 上 “有效的括号” 这道简单算法题的分析与解答:

题目描述


给定一个只包含括号字符 (){}[] 的字符串 s,判断字符串是否有效。


有效字符串需满足:


  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。


例如,字符串 "()""()[]{}" 是有效的,而 "(]""([)]" 是无效的。

解题思路


可以使用栈(Stack)这种数据结构来解决此问题。


  • 遍历输入的字符串 s
  • 当遇到左括号时,将其压入栈中。
  • 当遇到右括号时,检查栈顶元素:
  • 如果栈为空,说明没有与之匹配的左括号,直接返回 false
  • 如果栈顶元素是与之对应的左括号类型,则将栈顶元素弹出,表示匹配成功。
  • 如果栈顶元素不是与之对应的左括号类型,返回 false
  • 遍历完整个字符串后,如果栈为空,说明所有的括号都匹配成功,返回 true;否则,返回 false

示例代码(以 Python 为例)


def isValid(s):
    stack = []
    brackets_dict = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in "([{":
            stack.append(char)
        elif char in ")]}":
            if not stack:
                return False
            if stack[-1] == brackets_dict[char]:
                stack.pop()
            else:
                return False
    return not stack


在上述代码中:


  • 首先创建了一个空栈 stack 和一个字典 brackets_dict,用于存储右括号与左括号的对应关系。
  • 然后遍历字符串 s,根据字符是左括号还是右括号进行相应的操作。
  • 最后根据栈是否为空来判断字符串中的括号是否有效。


其他编程语言如 Java、C++ 等也可以按照类似的思路实现,只是语法上会有所不同。例如 Java 实现如下:


import java.util.Stack;
public class ValidBrackets {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top!= '(') || (c == ']' && top!= '[') || (c == '}' && top!= '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}


在 Java 代码中,利用了 Java 内置的 Stack 类来实现栈的功能,同样按照上述的思路对输入字符串进行处理以判断括号的有效性。

相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
41 0
|
2月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
29 2
|
2月前
|
算法 C++
Leetcode第二十二题(括号生成)
这篇文章讨论了如何使用递归算法解决LeetCode第22题“括号生成”的问题,提供了两种C++的实现方法,目的是生成所有有效的括号组合。
21 0
Leetcode第二十二题(括号生成)
|
2月前
|
存储 C++ 容器
Leetcode第二十题(有效的括号)
这篇文章介绍了如何使用栈来解决LeetCode第20题“有效的括号”问题,提供了两种方法:数组栈和容器栈,以及相应的C++代码实现。
19 0
|
4月前
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
76 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
4月前
|
算法
LeetCode第22题括号生成
该文章介绍了 LeetCode 第 22 题括号生成的解法,通过回溯算法生成所有可能的括号组合,在递归过程中根据左右括号数量的条件进行剪枝,从而得到有效的括号组合。
LeetCode第22题括号生成
|
4月前
|
存储 算法
LeetCode第20题有效的括号
该文章介绍了 LeetCode 第 20 题有效的括号的解法,通过分析有效括号的特征,使用栈结构存储括号关系,判断遇到右边括号时栈顶是否有匹配的左边括号,从而解决问题,同时总结了栈的先进后出结构可用于解决有规律的符号匹配问题。
LeetCode第20题有效的括号
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
54 6
|
4月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
70 2
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
52 1