20.有效的括号

ゝ一纸荒年。 2022-09-10 13:12 188阅读 0赞

题目描述：

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

有效字符串需满足：

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

示例1：

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

示例2：

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

解题：

首先可以考虑使用 Map 加 Stack 的组合来解决。将大中小括号以 key-value 值的形式存储于 map 中，左括号为 key，右括号为 value。之后遍历待校验的括号字符串，如果 map 中有此元素对应的 key 值，则将该元素压栈，如果map 中没有此元素对应的 key 值，则判断该元素是否与栈中的栈顶元素相等，如果相等，则做弹栈操作，如果不相等，则直接 false 返回。处理完成之后，去判断栈是否是空的，如果是空的，则证明所有括号匹配，返回 true，否则返回 false。

实例：待校验的括号为：str = "()"。

最开始的时候，map 中已经有 \{('(', ')'), ('\[', '\]'), ('\{', '\}')\} 三组键值对了。遍历循环 s 时：

当 i = 0 时，temp = '('，此时 map 中包含此 temp 的 key 值，所以进行压栈操作，将 '(' 压入 stack 栈中；

当 i = 1 是，temp = ')'，此时 map 中不包含此 temp 的 key 值，此时，栈顶元素为 '('，map 中与此 key 值相等的 value 的值为 ')'，此 value 与 temp 相等，则进行弹栈操作。

此时发现待校验的括号已处理完成，同时栈为空，则返回 true。

代码如下：

if (s.length() % 2 != 0) {
        return false;
    }
    if (s.equals("")) {
        return true;
    }
    Map<Character, Character> map = new HashMap<>(3);
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (map.containsKey(c)) {
            stack.push(c);
        } else {
            if (!stack.empty() && map.get(stack.peek()) == c) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.empty();

还有一种处理方法是使用字符串替换的方法，即将待校验的字符串中所有的 "()"、"\[\]"、"\{\}" 子串全都用 "" 来替换，最后判断待校验字符串是否等于 ""，如果是，则返回 true，如果不是，则返回 false。代码如下：

if (s.length() % 2 != 0) {
        return false;
    }
    if (s.equals("")) {
        return true;
    }
    int length = s.length() / 2;
    while (length > 0) {
        s = s.replace("{}", "").replace("[]", "").replace("()", "");
        length --;
        System.out.println(s);
    }
    return s.isEmpty();

我愿称此方法为最简，但是在中兴效率上却是不敢恭维~