当前位置：首页 > news >正文

LeetCode -- Distinct Subsequences

news 来源：原创 2024/5/19 12:28:58

题目描述：

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.

这道题目一开始没看懂什么意思，以为问的是在S和T中找出不同的子序列数。仔细读了几遍发现，不是在求子序列数，而是求，对于S来说，有多少种不同的删除操作可以得到T？ 因此，本题问的不是不同的子序列数，而是不同的删除操作数。（根据题目的例子，S经过3种不同的删除操作可以变为T）

思路：
就题目给的字符串分析：S = "rabbbit" T="rabbit"
当s为空，无法找到任何字串
当t为空，操作数为1，就是全部删除
先看s = "r"的情况，
s = "r" t = "r" return 1
s = "r" t = "ra","rab","rabb"... return 0 ，因为无论如何删除，s都无法成为t

再看s = "ra" 的情况,t = "ra"时，要计算s="ra"并且t="ra"不同的删除操作数，就等于求：
s="r"并且t="ra"时不同的删除操作数(0) ,再比较如果s最后1位(a)==t的最后一位(a)，则需要加上s=="r" 并且t=="r"的不同操作数（1）。

此题存在递推关系，考虑DP。

得到递推公式：

if s[i-1] == t[i-1] :
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
else :
dp[i][j] = dp[i-1][j]

实现代码：

public class Solution {
    public int NumDistinct(string s, string t) {
        if(string.IsNullOrWhiteSpace(s)){
		return 0;
	}     
	if(string.IsNullOrWhiteSpace(t)){
		return 1;	
	}
	
	var dp = new int[s.Length+1,t.Length + 1];
	
	for(var i = 0;i < s.Length + 1; i++){
		dp[i,0] = 1;
	}
	
	for(var j = 1; j < t.Length + 1; j++){
		dp[0,j] = 0;
	}
	
	for(var i =1 ;i < s.Length + 1; i++){
		for(var j = 1; j < t.Length + 1; j++){
			if(s[i-1] == t[j-1]){
				dp[i,j] = dp[i-1,j] + dp[i-1,j-1];
			}
			else{
				dp[i,j] = dp[i-1,j] ;
			}
		}
	}
	
	return dp[s.Length, t.Length];
    }
}