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();
      }
    }
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务