LeetCode 有效的括号

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

有效字符串需满足：

1、左括号必须用相同类型的右括号闭合。

2、左括号必须以正确的顺序闭合。

注意：空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true


示例 2:

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


示例 3:

输入: "(]"
输出: false


示例 4:

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


示例 5:

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

题解(使用栈)

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

执行用时 :3 ms, 在所有 Java 提交中击败了56.70%的用户

内存消耗 :37.5 MB, 在所有 Java 提交中击败了5.00%的用户

题解2(官方题解：增加一个map数据结构)

class Solution {
  private HashMap<Character, Character> mappings;
  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (this.mappings.containsKey(c)) {
        char topElement = stack.empty() ? '#' : stack.pop();
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        stack.push(c);
      }
    }
    return stack.isEmpty();
  }
}