題目地址(20. 有效的括號)

https://leetcode.cn/problems/valid-parentheses/

題目描述

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

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
每個右括號都有一個對應的相同類型的左括號。

前置知識

公司

思路

• 對于最近相關性題目，一般首先考慮使用棧

關鍵點

• Go的棧，這里使用切片實現
• 特別注意else if len(stack) > 0 && stack[len(stack) - 1] == s[i]中第一個條件

代碼

• 語言支持：Go

Go Code:

func isValid(s string) bool {
    if len(s) % 2 == 1 {
        return false
    }
    n := len(s)
    stack := make([]byte, 0)

    for i := 0; i < n; i++ {
        if s[i] == '(' {
            stack = append(stack, ')')
        } else if s[i] == '[' {
            stack = append(stack, ']')
        } else if s[i] == '{' {
            stack = append(stack, '}')
        } else if len(stack) > 0 && stack[len(stack) - 1] == s[i] {
            stack = stack[:len(stack) - 1]
        } else {
            return false
        }
    }
    return len(stack) == 0
}

復雜度分析

令 n 為數組長度。

• 時間復雜度：
• 空間復雜度：