链接
题目.
难度:
high
解答：
dp用熟了反而觉得简单了。s字符串增加一个字符，要么这个字符与t的最后一个字符相同，要么不相同
package main
import "fmt"
func numDistinct(s string, t string) int {
if len(s) < len(t) {
return 0
}
if len(t) == 0 {
return 1
}
dp := make([][]int, len(s)+1)
for i := 0; i <= len(s); i++ {
dp[i] = make([]int, len(t)+1)
dp[i][0] = 1
}
for j := 1; j <= len(t); j++ {
for i := j; i <= len(s); i++ {
dp[i][j] = dp[i-1][j]
if s[i-1] == t[j-1] {
dp[i][j] += dp[i-1][j-1]
}
}
}
return dp[len(s)][len(t)]
}
func main() {
fmt.Println(numDistinct("rabbbit", "rabbit")) //3
fmt.Println(numDistinct("babgbag", "bag")) //5
}
复杂度分析
time
O(m*n)
space
O(m*n)
执行结果
执行用时 :
4 ms
, 在所有 Go 提交中击败了
50.00%
的用户
内存消耗 :
7.4 MB
, 在所有 Go 提交中击败了
18.37%
的用户