目 录CONTENT

文章目录

手撕 | 括号匹配问题

RobKing
2023-09-25 / 0 评论 / 0 点赞 / 168 阅读 / 577 字

手撕 | 括号匹配问题

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
}
0

评论区