括号匹配

括号匹配题目给定一个只包括'(‘,’)’,'{‘,’}’,'[‘,’]’的字符串,判断字符串是否有效。有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例1:输入:”()”输出:true示例2:输入:”()[]{}”输出:true示例3:输入:”(]”输出:false示例4:输入:”([)]”输出:false…

大家好,欢迎来到IT知识分享网。

题目

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

有效字符串需满足:

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

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

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

示例 1:

输入: “()”

输出: true

示例 2:

输入: “()[]{}”

输出: true

示例 3:

输入: “(]”

输出: false

示例 4:

输入: “([)]” 输出: false

示例 5:

输入: “{[]}”

输出: true

LeetCode 地址:https://leetcode-cn.com/problems/valid-parentheses

解题思路

这道题考察的是就是验证括号的对称性,比如“([{}])”这种字符串就是正确的,应该返回 true,而“([{})]”这种字符串就是错误的,应该返回 false。

从上面的题目可以看出,括号总共分为三类:小括号、中括号和大括号,那么我们可以利用栈先进后出的特性,将所有左边的括号(“(”、“[”、“{”)先入栈,然后再碰到右括号时,让它与栈顶的元素进行匹配,比如当遇到“)”时,如果栈顶是“(”,则说明匹配成功,栈顶元素出栈再继续字符串循环的流程,如果匹配错误就直接返回 false。

假设我们要匹配字符串“(([]))”是否合法?那么执行流程就是这样的。

首先遇到左边括号,先入栈:

括号匹配

接下来又是左边括号,继续入栈:

括号匹配

然后又是左边括号,继续入栈:

括号匹配

接下来是右边括号,与栈顶元素匹配,“[]”为一对合法的括号,匹配成功栈顶元素出栈:

括号匹配

接下来又是右边括号,与栈顶元素匹配,“()”为一对合法的括号,匹配成功栈顶元素出栈:

括号匹配

接下来又是右边括号,与栈顶元素匹配,“()”为一对合法的括号,匹配成功栈顶元素出栈:

括号匹配

当字符串循环结束并且栈为空栈时,则证明此字符串的括号匹配合法,最终的效果如下图所示:

括号匹配

那么接下来我们就用代码来实现一下整个过程…

实现代码一

public boolean isValid(String s) {
    int slen = s.length(); // 括号的长度
    if (slen % 2 == 1) { // 括号不是成对出现直接返回 false
        return false;
    }
    // 把所有对比的括号存入 map,对比时用
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');
    // 定义栈,用于存取括号(辅助比较)
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < slen; i++) { // 循环所有字符
        char c = s.charAt(i);
        if (map.containsKey(c)) { // 为右边的括号,如 ')'、'}' 等
            if (stack.isEmpty() || stack.peek() != map.get(c)) { // 栈为空或括号不匹配
                return false;
            }
            stack.pop(); // 是一对括号,执行出栈(消除左右括号)
        } else { // 左边括号,直接入栈
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

我们在 LeetCode 中提交一下代码,执行结果如下:

括号匹配

代码解析

以上代码的 map 集合是用于定义括号的匹配规则,比如“)”对应的匹配值是“(”,“]”的匹配值是“[”等,然后我们再去循环待验证的字符串,遇到左括号直接入栈,遇到右括号让它与栈顶元素匹配,等到整个字符串循环结束,如果栈为空则说明字符串的括号合法。

复杂度分析

时间复杂度:O(n),遍历了一遍整个字符串。空间复杂度:O(n)。

实现代码二

除了使用栈之外,我们还可以使用借助 Java 中的 replace 方法来实现,我们可以循环的消除字符串中的括号,比如将“()”或“[]”或“{}”循环得替换为空,最后在执行完成之后如果字符串为空,则说明字符串中的括号是合法的,具体实现代码如下:

public boolean isValid(String s) {
        int len;
        do {
            len = s.length();
            // 消除成双成对的符号
            s = s.replace("()", "").replace("[]", "").
                    replace("{}", "");
        } while (len != s.length()); // 不能再进行替换了,replace 方法没有替换任何字符
        return s.length() == 0;
    }

我们在 LeetCode 中提交一下代码,执行结果如下:

括号匹配

从运行结果来看,二者的执行效率相差还是很明显的:

括号匹配

总结

本文我们讲了一道 bilibili 的笔试真题,同时它也是栈的经典面试题,我们可以借助栈的特性(先进后出)将所有的左括号入栈,当遇到右括号时让它与栈顶元素进行匹配,当字符串循环结束栈为空时,则说明此字符串的括号是合法的。当然我们在实际面试中,也可以使用 Java 的 replace 方法作为一个保底的实现方案,因为 replace 方法的实现相对更简单一些,只是性能不怎么好。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/9774.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信