手撕 | 括号匹配问题

20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

func isValid(s string) bool {
    size := len(s)
    if size % 2 != 0 {
        return false
    }
    st := make([]rune, 0)
    for _, v := range s {
        if v == '(' || v == '[' || v == '{' {
            st = append(st, v)
        }else {
            if len(st) == 0 {
                return false
            }
            top := st[len(st)-1]
            st = st[:len(st)-1]
            if (v == ')' && top != '(') || (v == ']' && top != '[') || (v == '}' && top != '{') {
                return false
            }
        }
    }
    return len(st) == 0
}

678. 有效的括号字符串

给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。

有效字符串符合如下规则：

• 任何左括号 '(' 必须有相应的右括号 ')'。
• 任何右括号 ')' 必须有相应的左括号 '(' 。
• 左括号 '(' 必须在对应的右括号之前 ')'。
• '*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串。
• 一个空字符串也被视为有效字符串。

func checkValidString(s string) bool {
    // 思路：通过两个栈保存下标，一个包括左括号，一个保存*号。遍历当为）时先匹配左括号栈，再匹配*栈。
    // 最后可能两个栈还有元素，如果*栈有元素没问题，继续匹配两个栈，保证最后左括号栈为空
    var leftStk, asteriskStk []int
    for i := range s {
        if s[i] == '(' {
            leftStk = append(leftStk, i)
        }else if s[i] == '*' {
            asteriskStk = append(asteriskStk, i)
        }else if len(leftStk) != 0 {
            leftStk = leftStk[:len(leftStk)-1]
        }else if len(asteriskStk) != 0 {
            asteriskStk = asteriskStk[:len(asteriskStk)-1]
        }else {
            return false
        }
    }
    // 栈中多余的元素
    i := len(leftStk) - 1
    for j := len(asteriskStk) - 1; i >= 0 && j >= 0; i, j = i - 1, j - 1 {
        // 左括号必须在前面，*才可以匹配
        if leftStk[i] > asteriskStk[j] {
            return false
        }
    }
    // 最终 左括号栈 不能有元素, 但是 *栈 可以有元素，因为可以是空
    return i < 0
}