java中如何判断有效的括号

这篇文章主要介绍java中如何判断有效的括号，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

问题

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

有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

实例

示例 1:
输入: "()"
输出: true

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

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

题解

栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；

Code(golang)

func isValid(s string) bool {
    if s == "" {
        return true
    }

    //栈
    stack := []string{}

    //hash存放对应关系
    m := map[string]string {
        ")":"(",
        "}":"{",
        "]":"[",
    }

    for i := 0; i < len(s); i++ {
        str := string(s[i])
        if str == "(" || str == "{" || str == "[" {
            stack = append(stack, str) //入栈
        } else if len(stack) > 0 && stack[len(stack)-1] == m[str] {
            //栈顶与当前str对应的hash是否一致 若一致则删除栈顶元素
            stack = stack[:len(stack)-1]
        } else {
            return false
        }
    }

    //若栈不为空 则有无效括号
    if len(stack) > 0 {
        return false
    }

    return true
}

复杂度分析

时间复杂度: 最坏情况O(n)    空间复杂度: O(n+m),m表示字符集，本题中字符串只包含 6 种括号,栈中的字符数量为 O(n)，哈希映射使用的空间为 O(6)，相加即可得到总空间复杂度

以上是“java中如何判断有效的括号”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！