Java版LeetCode

Appearance

20. 有效的括号 ​

栈 字符串

题目 ​

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

题解 ​

java
/**
 * 括号对缓存
 */
private static final Map<Character, Character> BRACKET_PAIR = new HashMap<>(3);

static {
    BRACKET_PAIR.put('(', ')');
    BRACKET_PAIR.put('{', '}');
    BRACKET_PAIR.put('[', ']');
}

public boolean isValid(String s) {
    // 用于暂时存放未匹配完的开括号
    Stack<Character> container = new Stack<>();
    for(int i = 0, length = s.length(); i < length; i ++) {
        Character bracket = s.charAt(i);
        // 弹出括号为闭括号
        if(!BRACKET_PAIR.containsKey(bracket)
            // 若待匹配栈为空或待匹配开括号与弹出闭括号不能配对
            && (container.isEmpty() || !bracket.equals(BRACKET_PAIR.get(container.pop())))) {
            return false;
        }

        // 开括号 暂存待匹配
        if(BRACKET_PAIR.containsKey(bracket)) {
            container.push(bracket);
        }

        // 否则 弹出的闭括号能和暂存的开括号配对 弹出并跳过
    }

    return container.isEmpty();
}

public boolean isValid2(String s) {
    // 括号原子是成对存在的 直接通过替换的方式快速处理
    // 效率较低
    while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
        s = s.replace("()", "");
        s = s.replace("{}", "");
        s = s.replace("[]", "");
    }

    return s.isEmpty();
}