UCloud笔试 编程第二题

https://leetcode.cn/problems/valid-parenthesis-string/solutions/992347/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/

力扣原题↑

package main

import "fmt"

func isValidString(s string) bool {
    if s == "" {
        return true
    }
    // write code here
    var leftCount = 0
    var starCount = 0
    var rightCount = 0
    for _, v := range s {
        if v == rune('(') {
            leftCount++
        } else if v == rune('*') {
            starCount++
        } else if v == rune(')') {
            rightCount++
        }
    }
    res := leftCount - rightCount
    if res == 0 {
        return true
    } else if (res > 0 && res-starCount <= 0) || (res < 0 && res+starCount >= 0) {
        return true
    }
    return false
}

func main() {
    ok := isValidString("((*)))")
    fmt.Println(ok)
}

大概意思就是( )互相匹配，左括号一定要在右括号左边才能算一个。* 可以代替任意括号，也可以视为空字符。要得出结果是否合法。

显然这上面的代码没有考虑到)(的情况，所以我的测试通过只有75%，最好是用栈的形式去实现这个代码：

func checkValidString(s string) bool {
    var leftStk, starStk []int
    for i, val := range s {
        if val == '(' {
            leftStk = append(leftStk, i)
        } else if val == '*' {
            starStk = append(starStk, i)
        } else if len(leftStk) > 0 {
            leftStk = leftStk[:len(leftStk)-1]
        } else if len(starStk) > 0 {
            starStk = starStk[:len(starStk)-1]
        } else {
            return false
        }
    }
    i := len(leftStk) - 1
    for j := len(starStk) - 1; i >= 0 && j >= 0; i, j = i-1, j-1 {
        if leftStk[i] > starStk[j] {
            return false
        }
    }
    return true
}

    for i, val := range s {
        if val == '(' {
            leftStk = append(leftStk, i)
        } else if val == '*' {
            starStk = append(starStk, i)
        } else if len(leftStk) > 0 {
            leftStk = leftStk[:len(leftStk)-1]
        } else if len(starStk) > 0 {
            starStk = starStk[:len(starStk)-1]
        } else {
            return false
        }
    }

这一段，意在将左括号和星号的下标记录进栈里（注意是下标）。后面两个 if 判断是用来判断出现了 ) 的情况，这里的 ) 如果合理的话，肯定是出现在有 * 或者 ( 的前提下，这样就能相互抵消，即这两个 else if ：

        else if len(leftStk) > 0 {
            leftStk = leftStk[:len(leftStk)-1]
        } else if len(starStk) > 0 {
            starStk = starStk[:len(starStk)-1]
        } 

优先匹配 ( ，没有再匹配 * ，如果还没有，那就说明这个 ) 前面根本没有能抵消它的 ( 和 * 。

如果这之前都是合理的，那么这里从栈的头部开始看，也就是数组末尾，看剩下的 ( 和 * ，这样是为了让 * 能充当 ) 去抵消 ( ，所以 * 要在 ( 之后，这也是为什么用下标来作为入栈元素的原因，当有一个 ( 的下标大于 * 的时候，那么这个最末尾的 ( 不会被抵消掉了而残余下来，也就说明最终会残余多一个 (，不符合合理条件。

    i := len(leftStk) - 1
    for j := len(starStk) - 1; i >= 0 && j >= 0; i, j = i-1, j-1 {
        if leftStk[i] > starStk[j] {
            return false
        }
    }