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)，相加即可得到总空间复杂度

本文参考链接：https://www.yisu.com/zixun/593660.html