Distinct Subsequences
Total Accepted: 38466 Total Submissions: 143567My Submissions
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
num=[0]
self.CountSubsequence(s,t,0,0,num)
return num[0]
def CountSubsequence(self,father_sequence,child_sequence,index_father,index_child,num):
#print(index_father,index_child)
len_father=len(father_sequence)
len_child=len(child_sequence)
if index_child==len_child:
num[0]+=1
#print("匹配到了相同的")
else:
#print("进入迭代")
for i in range(index_father,len_father):
if father_sequence[i]==child_sequence[index_child]:
self.CountSubsequence(father_sequence,child_sequence,i+1,index_child+1,num)
#这里num是一个列表，可以从外部访问的，所以不需要return
方法二：DP（Dynamic Programming, 动态规划）
此处参考陆草纯的解题报告将问题转化为“二维地图走法问题”。
我觉得他在文章里对转化为“二维地图走法问题”说明的不清楚：
疑问一：为何走的时候只能“对角线走”和“向右向下走”，不能“向下向右走”。
疑问二：为何字符判断相等时，是“对角线走”和“向右向下走”相加；而字符不等时，只能“向右向下走”。
经过自己的思考，我来说一下我的理解：
一个子字符串t'，一个父字符串s'，两者一点一点相加。最终子字符串的长度加到T的长度，父字符串的长度加到S的长度。
当字符不等时，也就是说，父字符串s‘中新加的元素s'[i]无法对走法有贡献，所以可以删掉，于是就变成了“向右向下走”
字符相等时，父字符串s'中新加的元素s'[i]对走法有贡献，所以对角线是可以取的；同时“向右向下走”（即删掉s'[i]）也是可行的；由于两者是不同的走法，自然要相加。
显然，DP的思路是从0开始一点一点增加子字符串的长度，最终达到我们想要匹配的字符串长度。显然不能减少字符串t'的长度。
大家画个图就明白了，以s' 为纵轴，t'为横轴。下面直接上AC的python代码：
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
#s is father_sequence
#t is child_sequence
len_father=len(s)
len_child=len(t)
dp=[[0 for i in range(len_child)] for j in range(len_father)]
if len_father==0 or len_child==0:
result=0
else:
#dp=[[0 for i in range(len_child)] for j in range(len_father)]
if s[0]==t[0]:
dp[0][0]=1
for i in range(1,len_father):
dp[i][0]=dp[i-1][0]
if s[i]==t[0]:
dp[i][0]+=1 for i in range(1,len_father):
for j in range(1,len_child):
if i>=j:
if s[i]==t[j]:
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
else:
dp[i][j]=dp[i-1][j]
result=dp[len_father-1][len_child-1]
return result