给定一个字符串Str，返回Str的所有子序列中有多少不同的字面值。
返回值=上+新-修正。
时间复杂度：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
}执行结果如下：
