java中如何判斷有效的括號

這篇文章主要介紹java中如何判斷有效的括號，文中介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們一定要看完！

問題

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。

有效字符串需滿足：

    左括號必須用相同類型的右括號閉合。
    左括號必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。

實例

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

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

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

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

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

題解

棧先入后出特點(diǎn)恰好與本題括號排序特點(diǎn)一致，即若遇到左括號入棧，遇到右括號時將對應(yīng)棧頂左括號出棧，則遍歷完所有括號后 stack 仍然為空；

Code(golang)

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

    //棧
    stack := []string{}

    //hash存放對應(yīng)關(guān)系
    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] {
            //棧頂與當(dāng)前str對應(yīng)的hash是否一致 若一致則刪除棧頂元素
            stack = stack[:len(stack)-1]
        } else {
            return false
        }
    }

    //若棧不為空 則有無效括號
    if len(stack) > 0 {
        return false
    }

    return true
}

復(fù)雜度分析

時間復(fù)雜度: 最壞情況O(n)    空間復(fù)雜度: O(n+m),m表示字符集，本題中字符串只包含 6 種括號,棧中的字符數(shù)量為 O(n)，哈希映射使用的空間為 O(6)，相加即可得到總空間復(fù)雜度

以上是“java中如何判斷有效的括號”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！