【力扣刷题第一天-1】 有效的括号

前言一、题目描述二、解题思路三、示例代码总结

  本题主要利用「栈」这一数据结构来解决。

提示：以下是本篇文章正文内容，编程语言为Java

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

链接：有效的括号

  本题比较简单，可以很容易想到利用栈这一数据结构来解决。
  我们遍历给定的字符串 s。此时可以分为两种情况：
  1）当遇到左括号时直接把它放入栈顶。
  2）当遇到右括号时。我们就要弹出栈顶元素，看是否和当前括号匹配，若不匹配则该括号无效，直接返回 false。这里要特别注意栈为空的情况。
  遍历结束，若栈为空，则所有括号都有效，返回 true。否则，说明左括号多，返回 false。

class Solution {
    public boolean isValid(String s) {
        Deque st=new linkedList<>();
        for(char c:s.toCharArray()){
            if(c=='('||c=='['||c=='{'){
                st.push(c);
            }
            else if(st.isEmpty()||c==')'&&st.pop()!='('||c=='}'&&st.pop()!='{'||c==']'&&st.pop()!='['){
                return false;
            }

        }
        return st.isEmpty();

    }
}

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

  Java可以用Deque st=new linkedList<>()来初始化栈，不推荐用Stack。
  其中，linkedList是一个双端队列，里面封装了栈的常用方法，如下表所示：