LC115. 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 "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.
求S里包含多少T的非重复子序列。最开始没什么思路，看了discuss👆，豁然开朗XD。memo[i][j]表示S[0-j]包含多少T[0-i]的子序列。空字符串永远被包含，所以第一行置为1，其后每一行的第一个元素为0.如果对于(x, y), T[x] == S[y], 那么memo[x][y] = memo[x-1][y-1] + memo[x][y-1]. 同时增加了一个相同的字母，那么匹配的数目就是都不增加这个字母的匹配数目和S不增加这个字母的匹配数目之和。
public class Solution {
public int numDistinct(String s, String t) {
char[] sarr = s.toCharArray();
char[] tarr = t.toCharArray();
int[][] memo = new int[tarr.length+1][sarr.length+1];
for(int i = 0; i <= sarr.length; i++) memo[0][i] = 1;
for(int i = 1; i <= tarr.length; i++){
for(int j = 1; j <= sarr.length; j++){
if(sarr[j - 1] == tarr[i - 1]) memo[i][j] += memo[i-1][j-1];
memo[i][j] += memo[i][j-1];
}
}
return memo[tarr.length][sarr.length];
}
}
O(mn), O(mn)