一、问题描述

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

1.左括号必须用相同类型的右括号闭合。 2.左括号必须以正确的顺序闭合。

注意：空字符串也被视为有效。

二、方案一：使用栈

1、思路

我们可以使用栈来解决这个问题。遍历字符串，对于每个字符：

• 如果是左括号，则将其对应的右括号压入栈中。
• 如果是右括号，则检查栈顶元素是否与之匹配。如果匹配，则弹出栈顶元素；否则，字符串无效。
• 遍历结束后，如果栈为空，则字符串有效；否则，字符串无效。

提示：

• 使用栈（先进后出）

2、代码实现

func isValid(s string) bool {
    stack := []rune{}
    // 定义括号映射
    brackets := map[rune]rune{
        ')': '(',
        '}': '{',
        ']': '[',
    }
    for _, ch := range s {
        if _, ok := brackets[ch]; ok {
            // 如果是右括号
            if len(stack) == 0 || stack[len(stack)-1] != brackets[ch] {
                return false
            }
            // 匹配，弹出栈顶元素
            stack = stack[:len(stack)-1]
        } else {
            // 如果是左括号，压入栈
            stack = append(stack, ch)
        }
    }
    // 栈为空则有效
    return len(stack) == 0
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需要遍历一次字符串。
• 空间复杂度：O(n)，最坏情况下，字符串中的所有字符都是左括号，它们都需要被放入栈中。

三、总结

方案一使用栈来解决问题，具有直观和易于理解的特点。方案二使用计数器，减少了空间复杂度，但代码相对复杂，且对于非括号类型的字符处理不够直观。在实际应用中，方案一更为常见和推荐。