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 =
S =
"rabbbit"
, T = "rabbit"
Return
Another DP! And a two dimensional one.3
.S = "rabbbit";
T = "rabbit";
r a b
0 1 2 3
0 1 0 0 0
r 1 1 1 0 0
a 2 1 1 1 0
b 3 1 1 1 1
b 4 1 1 1 2
Let num[S.length() + 1][T.length() + 1] represents the number of subsequences of any substrings of S can be generated from any substrings of T. num[i][j] represents the number of subsequences of S.substring(0, i) from T.substring(0, j).
num[i][0] equals 1 because an empty string is a subsequence of any string.
num[0][j] equals 0 because an empty string has no subsequence string.
if S = "rabc", then number of subsequence formed by T = "rab" equals number of subsequence of "rab" formed by T: num[i][j] = num[i - 1][j] if s.charAt(i - 1) != s.charAt(j - 1);
if S = "rabb", then besides number of subsequence of "rab", we also need to add number of sequence of "rab" formed by "ra", because when we add 'b', we can form new subsequences: num[i][j] += num[i - 1][j - 1].
public class DistinctSubsequences { public static int sum; public int numDistinct(String S, String T) { if (S == null || T == null) return 0; int[][]nums = new int[S.length() + 1][T.length() + 1]; for(int i = 0; i <= S.length(); i++) nums[i][0] = 1; for (int i = 1; i <= S.length(); i++) { for (int j = 1; j <= T.length(); j++) { nums[i][j] = nums[i - 1][j]; if (S.charAt(i - 1) == T.charAt(j - 1)) nums[i][j] += nums[i - 1][j - 1]; } } return nums[S.length()][T.length()]; } }
I have a solution using less space:
ReplyDeletepublic class Solution {
public int numDistinct(String s, String t) {
if(s == null || t == null || t.length() == 0) return 0;
int[] dp = new int[t.length()];
for(int i = 0; i=0; j–){
if(c == t.charAt(j)){
dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
}
}
}
return dp[t.length()-1];
}
}
URL: http://traceformula.blogspot.com/2015/08/distinct-subsequences.html