不同的子序列

[编程题]不同的子序列

热度指数：19677 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？

字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
例如：

S="nowcccoder", T = "nowccoder"

返回3

示例1

输入

"nowcccoder","nowccoder"

输出

算法知识视频讲解

Python

🇮🇹ForzaMilan！

class Solution:
    def numDistinct(self , S , T ):
        # write code here
        m = len(S)
        n = len(T)
        if m < n:
            return(0)
        elif m * n == 0 or S == T:
            return(1)
        else:
            res = [[0 for i in range(m)] for j in range(n)]
            for j in range(m):
                if S[j] == T[0]:
                    for x in range(j,m):
                        res[0][x] += 1
            for i in range(1,n):
                for j in range(1,m):
                    if S[j] == T[i]:
                            res[i][j] = res[i-1][j-1]+res[i][j-1]
                    else:
                        res[i][j] = res[i][j-1]
            return(res[n-1][m-1])

编辑于 2020-06-03 14:51:35 回复(0)