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

链接: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)的对象堆栈。栈是一种非常常见的数据结构,它采用典型的先进后出的操作方式完成的。每一个栈都包含一个栈顶,每次出栈是将栈顶的数据取出,如下:

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

示例代码:

//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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

T4312 最大出栈顺序

题目描述 给你一个栈和n个数,按照n个数的顺序入栈,你可以选择在任何时候将数 出栈,使得出栈的序列的字典序最大。 输入输出格式 输入格式: 输入共2行。...

3628
来自专栏云霄雨霁

数据结构----队列

1070
来自专栏程序你好

如何将Array转换为List?

可以使用 Arrays.asList() 方法, 该方法接受一个数组作为输入,并返回一个列表作为输出。

952
来自专栏技术专栏

Scala入门与进阶(三)- 函数

默认参数:在函数定义时,允许指定参数的默认值 $SPARK_HOME/conf/spark-defaults.conf

1113
来自专栏Danny的专栏

Java基础——List接口

  如上图:ArrayList, LinkedList, Vector, Stack是List4个常用的实现类。

1012
来自专栏Java学习网

Java面试题系列之基础部分(四)——每天学5个问题

Java基础部分学习的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语法,集合的语法,io的语法,虚拟机方面的语法,这些都是最基...

2488
来自专栏从零开始学 Web 前端

从零开始学 Web 之 ES6(二)ES5的一些扩展

打印结果:Obj2下面的__proto__指向的原型对象中有Obj1的属性,相当于继承了Obj1属性。

1055
来自专栏算法修养

ZOJ 3932 Deque and Balls

There are n balls, where the i-th ball is labeled as pi. You are going to put n ...

2405
来自专栏天天

String

671
来自专栏指尖下的Android

简单算法之冒泡排序

外层循环控制循环次数,内层循环控制比对元素的个数,因为冒泡排序是两两比对,五个元素的数组只需要比对四次,因为最后一个元素没有可比对的元素,内层循环判断条件j <...

902

扫码关注云+社区

领取腾讯云代金券