[LeetCode] Valid Parentheses 验证括号是否有效闭合

简介: 链接:https://leetcode.com/problems/valid-parentheses/#/description难度:Easy题目:20.

链接https://leetcode.com/problems/valid-parentheses/#/description
难度:Easy
题目:20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

翻译:给定一个仅包含字符'(',')','{','}','['和']'的字符串,确定输入字符串是否有效。括号必须以正确的顺序关闭,“()”和“()[] {}”都是有效的,但“(]”和“([)]”不是。

思路:用数据结构——栈就可以实现。遍历字符串,把左括号压栈,碰到右括号就把栈的顶部元素拿出来与右括号匹配,匹配成功则顶部元素出栈,进入下一次循环,匹配不成功或者栈中无元素,则字符串不是有效闭合。直到所有元素遍历完,栈中无元素,即为有效闭合;如果所有元素遍历完了,栈中还有元素,则不是有效闭合。

基础概念

在 Java 中 Stack 类表示后进先出(LIFO)的对象堆栈。栈是一种非常常见的数据结构,它采用典型的先进后出的操作方式完成的。每一个栈都包含一个栈顶,每次出栈是将栈顶的数据取出,如下:


img_170fb333e7a571d4c0b11798a5aeef41.jpe

Stack 通过五个操作对 Vector 进行扩展,允许将向量视为堆栈。这个五个操作如下:


img_70406f460ed61f546a9230a0810bd9b2.jpe

示例代码:

//Create the Stack instance and add a couple of elements to it
Stack stack = new Stack();
String s1 = "element 1";
String s2 = "element 2";
stack.push(s1);
stack.push(s2);
System.out.println(stack.peek());
//element 2
//Find position of a certain element
int pos = stack.search("element 1");
System.out.println(pos);
//2
System.out.println(stack.pop());
System.out.println(stack.pop());
//element 2
//element 1
System.out.println(stack.empty());
//true

参考代码
Java

public class Solution {
    public boolean isValid(String s) {
        if(s==null || s.length()==0)
            return false;
        Stack<Character> parentheses = new Stack<Character>(); 
        for (int i = 0; i< s.length(); i++){
            char c = s.charAt(i); 
            if(c=='(' || c=='[' || c =='{')
                parentheses.push(c);
            else{
                if (parentheses.empty())
                    return false;
                if (c == ')' && parentheses.peek() != '(')
                    return false;
                if (c == ']' && parentheses.peek() !='[')
                    return false;
                if (c == '}' && parentheses.peek() !='{')
                    return false;
                parentheses.pop();
            }
        }
        return parentheses.empty();
    }
}

参考资料
http://outofmemory.cn/code-snippet/2087/java-usage-Stack-class

目录
相关文章
|
2月前
|
算法
LeetCode第22题括号生成
该文章介绍了 LeetCode 第 22 题括号生成的解法,通过回溯算法生成所有可能的括号组合,在递归过程中根据左右括号数量的条件进行剪枝,从而得到有效的括号组合。
LeetCode第22题括号生成
|
2月前
|
存储 算法
LeetCode第20题有效的括号
该文章介绍了 LeetCode 第 20 题有效的括号的解法,通过分析有效括号的特征,使用栈结构存储括号关系,判断遇到右边括号时栈顶是否有匹配的左边括号,从而解决问题,同时总结了栈的先进后出结构可用于解决有规律的符号匹配问题。
LeetCode第20题有效的括号
|
2月前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案,通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
22 6
|
2月前
|
算法 Python
【Leetcode刷题Python】括号匹配问题
一种解决括号匹配问题的Python实现方法,通过计算给定括号串的所有子串的最长合法括号子序列长度之和来确定权值。
17 0
|
2月前
|
机器学习/深度学习 Python
【Leetcode刷题Python】22. 括号生成
本文介绍了了LeetCode题目22的两种Python编程解决方案,题目要求生成所有可能的且有效的括号组合,包括暴力求解和回溯方法。
19 0
|
2月前
|
Python
【Leetcode刷题Python】20. 有效的括号
LeetCode上题目“20. 有效的括号”的Python解决方案,使用栈数据结构来验证括号序列的有效性。具体实现中,会在栈中预先放置一个特殊字符以避免在弹出操作时出现空栈错误,并通过匹配左右括号来判断括号序列是否有效。
20 0
|
3月前
|
算法 测试技术
力扣经典150题第五十一题:有效的括号
力扣经典150题第五十一题:有效的括号
29 0
|
4月前
力扣经典150题第二十五题:验证回文串
力扣经典150题第二十五题:验证回文串
29 0
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏