20. 有效的括号-字符串,栈(易)

题目描述

题目链接:https://leetcode-cn.com/problems/valid-parentheses/submissions/

题目要求:

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

解题思路

思路就是当左括号时, 存入栈中, 遍历到右括号的时候我们检查栈顶元素是不是对应左括号即可, 如果是就弹出, 不是直接返回false
注意右括号多出来的情况要特判一下, 也就是当遍历右括号时,如果栈内为空,则直接false.
最后直接返回stack.isEmpty()即可.

复杂度分析

T: O(n)
S: O(n)

代码

• 代码1, 正常代码

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

• 代码2, 存入左括号时直接存入对应右括号,逻辑更清晰

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