leetcode刷题-20有效的括号

小知识,大挑战!本文正在参与“程序员必备小知识”创作活动。

leetcode20-有效的括号

前文

本文为菜鸟的刷题记录,仅用作笔记使用,并非最佳解决方案。

题目信息

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

有效字符串需满足:

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

解题思路分析

解法1

本解法主要通过栈进行操作。首先对字符串进行遍历,如果遇到左括号,则将其放入到栈中。如果遇到右括号,那么首先从栈中提取栈顶元素。如果栈顶元素是与右括号匹配的左括号,则继续向前遍历。如果栈顶元素与右括号并不匹配,则说明栈顶元素与右括号并非是一对括号,则该字符串为无效字符串。当整个字符串遍历结束,如果栈中元素为空,则所有括号都达成匹配,则认为该字符串为有效字符串。 代码如下:

public boolean isValid(String s) {
    Stack stack = new Stack();
    for (int i = 0; i < s.length(); i++) {
        switch (s.charAt(i)){
            case '(':
            case '[':
            case '{':
                stack.add(s.charAt(i));
                break;
            case ']':
                if('[' == (char)stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
                break;
            case '}':
                if('{' == (char)stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
                break;
            case ')':
                if('(' == (char)stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
                break;
            default:
                return false;
        }
    }
    if(stack.empty()){
        return true;
    }else{
        return false;
    }
}
复制代码

解法2

本解法主要是通过字符串替换达成效果。将所有匹配的字符串均替换成空,如果最终结果为空字符串,则为有效字符串。否则,认为字符串无效。 代码如下:

public boolean isValid(String s) {
    while (s.indexOf("[]") > -1 || s.indexOf("()") > -1 || s.indexOf("{}") > -1){
        s = s.replace("[]","");
        s = s.replace("{}","");
        s = s.replace("()","");
    }
    if("".equals(s)){
        return true;
    }
    return false;
}
复制代码

复杂度分析

  • 时间复杂度 o(n)
  • 空间复杂度 o(n)

后记

  • 千古兴亡多少事?悠悠。不尽长江滚滚流。

作者:码中悍刀行
链接:https://juejin.cn/post/7017631196108554247
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录
关闭
目 录