LeetCode第二十题-有效的括号

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Valid Parentheses

问题简介：

给定一个只包含字符 ‘(’ , ‘)’ , ‘{’ , ‘}’ , ‘[’ , ‘]’ 的字符串，确定输入字符串是否有效

有效的条件：

必须使用相同类型的括号关闭左括号,

必须以正确的顺序关闭打开括号,

注意,空字符串也被视为有效.

举例

1.

输入: “()”

输出: true

2:

输入: “()[]”

输出: true

3:

输入: “(]”

输出: false

4:

输入: “([)]”

输出: false

5:

输入: “{[]}”

输出: true

解法一：

先用Map集合存储三种括号,再利用栈结构进行判断,因为第一个右括号出现时都要匹配最近的左括号,这符合栈结构先入后出的结构,即当右括号出现时与栈顶的元素判断

复杂度分析：

时间复杂度:o(n)遍历一遍字符串

空间复杂度:o(n)字符串n个字符的定义

注：

1.栈

后进先出的数据结构,只能在一端进行插入(称为压栈) 或删除 (称为出栈)数据的操作,JAVA 中,使用 java.util.Stack 类的构造方法创建对象

public class Stack extends vector

方法：

小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海