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中如何判斷有效的括號”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！