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. (i.e, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
Idea: Dynamic programming. Let dp[i][j] denote the number of distinct subsequence of S[0...i] and T[0...j]. If S[i]!=T[j], dp[i][j]=dp[i-1][j], since S[0...i-1] needs to contain T[0...j]; if S[i]==T[j], both two scenarios will be fine:
1) S[0...i-1] contains T[0...j]
2) S[0...j-1] contains T[0...j-1]
So dp[i][j]=dp[i-1][j]+dp[i-1][j-1].
Time: O(n^2) Space: O(n^2)
Code:
public class Solution {
public int numDistinct(String S, String T) {
int m=S.length();
int n=T.length();
int[][] dp=new int[m+1][n+1];
for(int i=0;i<m;i++)
dp[i][0]=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(S.charAt(i-1)==T.charAt(j-1))
dp[i][j]+=dp[i-1][j-1]+dp[i-1][j];
else
dp[i][j]+=dp[i-1][j];
}
}
return dp[m][n];
}
}
No comments:
Post a Comment