2021-08-15：给定一个字符串Str，返回Str的所有子序列中

原创

福大大架构师每日一题

修改于 2021-08-16 10:37:20

7880

修改于 2021-08-16 10:37:20

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-08-15：给定一个字符串Str，返回Str的所有子序列中有多少不同的字面值。

福大大答案2021-08-15：

返回值=上+新-修正。

时间复杂度：O(N)

空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    s := "aabb"
    ret := distinctSubseqII(s)
    fmt.Println(ret)
}

func distinctSubseqII(s string) int {
    if len(s) == 0 {
        return 0
    }
    m := 1000000007

    count := make([]int, 26)
    all := 1 // 算空集
    for _, x := range s {
        add := (all - count[x-'a'] + m) % m
        all = (all + add) % m
        count[x-'a'] = (count[x-'a'] + add) % m
    }
    return all - 1
}

func zuo(s string) int {
    if len(s) == 0 {
        return 0
    }
    m := 1000000007
    map0 := make(map[byte]int)
    all := 1 // 一个字符也没遍历的时候，有空集
    for i := 0; i < len(s); i++ {
        x := s[i]
        newAdd := all
        curAll := all
        curAll = (curAll + newAdd) % m
        if _, ok := map0[x]; ok {
            curAll = (curAll - map0[x] + m) % m
        } else {
            curAll = (curAll + m) % m
        }
        all = curAll
        map0[x] = newAdd
    }
    return all
}

执行结果如下：