leetcode: Distinct Subsequences
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
"AEC" is not).
Here is an example:
"rabbbit", T =
Solution and Precautions:
DP: let F(i, j) denote the number of ways for S…S[i] contain T..T[j], Then F(n-1, m-1) is our answer and we have
if(S[i] != T[j]) F(i, j) = F(i-1, j);
if(S[i] == T[j]) F(i, j) = F(i-1, j-1) + F(i-1, j);
Tips and Divergent thinking:
Be careful on the base case, and for the above recursive definition, recursive implementation might be easier to maintain than for loops.