给定两个字符串S和T,返回S子序列等于T的不同子序列个数有多少个?
字符串的子序列是由原来的字符串删除一些字符(也可以不删除)在不改变相对位置的情况下的剩余字符(例如,"ACE"is a subsequence of"ABCDE"但是"AEC"不是)
例如:
例如:
S="nowcccoder", T = "nowccoder"
返回3
"nowcccoder","nowccoder"
3
class Solution { public: int numDistinct(string S, string T) { int len=T.size(); vector<int> array(len+1); array[0]=1; for(int i=1;i<S.size()+1;i++){ for(int j=min(i,len);j>0;j--){ if(S[i-1]==T[j-1]) array[j]=array[j]+array[j-1]; } } return array[len]; } };
原理不多说,上面的大神已经说得很清楚了,下面晒出我的示意图和代码:
public int numDistinct(String S, String T) {
if (S == null || T == null || T.length() == 0 || S.length() < T.length()) {
return 0;
}
int sLen = S.length();
int tLen = T.length();
int[][] array = new int[sLen + 1][tLen + 1];
// 初始化第一行,字符串S为"",除了子字符串为""的情况,结果全部为0
for (int i = 1; i < tLen + 1; i++) {
array[0][i] = 0;
}
// 初始化第一列,子字符串为"",结果全部为1
for (int i = 0; i < sLen + 1; i++) {
array[i][0] = 1;
}
for (int i = 1; i < sLen + 1; i++) {
// j>i时子序列的长度大于源数列,结果为0,无需遍历
// 或者for (int j = 1; j <= Math.min(i, tLen); j++)
for (int j = Math.min(i, tLen); j > 0; j--) {
// 如果当前位置的字母不同
if (S.charAt(i - 1) != T.charAt(j - 1)) {
array[i][j] = array[i - 1][j];
} else {// 如果当前位置的字母相同
array[i][j] = array[i - 1][j] + array[i - 1][j - 1];
}
}
}
return array[sLen][tLen];
}
// 因为当前结果只取决于上一行结果的当前位置和后面一位,因此可以降维
public int numDistinct2(String S, String T) {
if (S == null || T == null || T.length() == 0 || S.length() < T.length()) {
return 0;
}
int sLen = S.length();
int tLen = T.length();
int[] array = new int[tLen + 1];
array[0] = 1;
for (int i = 1; i < sLen + 1; i++) {
for (int j = Math.min(i, tLen); j > 0; j--) {
if (S.charAt(i - 1) == T.charAt(j - 1)) {
array[j] = array[j] + array[j - 1];
}
}
}
return array[tLen];
}
/* * 思路:dp题。 * 状态定义:dp[i][j]代表s[0~i-1]中T[0~j-1]不同子串的个数。 * 递推关系式:S[i-1]!= T[j-1]: DP[i][j] = DP[i][j-1] (不选择S中的s[i-1]字符) * S[i-1]==T[j-1]: DP[i][j] = DP[i-1][j-1](选择S中的s[i-1]字符) + DP[i][j-1] * 初始状态:第0列:DP[i][0] = 0,第0行:DP[0][j] = 1 */ public class Solution { public int numDistinct(String S, String T) { int row = S.length() + 1; int col = T.length() + 1; int[][] dp = new int[row][col]; for (int i = 1; i < col; i++) { dp[0][i] = 0; } for (int i = 0; i < row; i++) { dp[i][0] = 1; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; 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[row - 1][col - 1]; } }
class Solution: def numDistinct(self , S , T ): # write code here m = len(S) n = len(T) if m < n: return(0) elif m * n == 0 or S == T: return(1) else: res = [[0 for i in range(m)] for j in range(n)] for j in range(m): if S[j] == T[0]: for x in range(j,m): res[0][x] += 1 for i in range(1,n): for j in range(1,m): if S[j] == T[i]: res[i][j] = res[i-1][j-1]+res[i][j-1] else: res[i][j] = res[i][j-1] return(res[n-1][m-1])
class Solution { /** * DP: 假设dp[i][j]是S中前i个字符构成的子串和T中前j个字符构成 * 的子串匹配得到的子序列数量,求dp[S.length()][T.length()] * 1. 初始条件dp[i][0],S的前i的任意子串与空串有一个匹配的序列,dp[i][0]=1 * 初始条件dp[0][j](j>0),S的空串与任意非空串无匹配的子序列,dp[0][j]=0 * 2. 转义条件,求dp[i][j]的值有两种情况: * 1)S[i-1]!=T[j-1], dp[i][j]=dp[i-1][j] S的i-1位置与T的j-1不匹配 * 那么符合的匹配序列数量和S的前i-1个字符的子串一样 * 2) S[i]==T[j-1], dp[i][j]=dp[i-1][j]+dp[i-1][j-1] S的i-1与T的j-1匹配 * 那么符合匹配的序列数等于前i-1就符合与T前j匹配的,加上S前i-1子串和 * T的前j-1子串匹配的。 */ public int numDistinct(String s, String t) { int[][] num = new int[s.length()+1][t.length()+1]; for(int i=0; i<=s.length(); i++){ num[i][0] = 1; } for(int i=1; i<=s.length(); i++){ for(int j=1; j<=t.length(); j++){ if(s.charAt(i-1)==t.charAt(j-1)){ num[i][j] = num[i-1][j] + num[i-1][j-1]; } else { num[i][j] = num[i-1][j]; } } } return num[s.length()][t.length()]; } }
class Solution { public: int numDistinct(string S, string T) { S=" "+S,T=" "+T; int n=S.length(),m=T.length(),i,j; vector<vector<int> > dp(n+1,vector<int>(m+1,0)); for(i=0;i<=n;i++) dp[i][0]=1; for(i=1;i<=n;i++) for(j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]; if(S[i]==T[j]) dp[i][j]+=dp[i-1][j-1]; } return dp[n][m]; } };
public class Solution { public int numDistinct(String S, String T) { if (S == null || T == null) return 0; if (S.equals("") || T.equals("")) return 0; //table[i][j]表示S[0~i]中有多少个T[0~j]的个数 int[][] table = new int[S.length()][T.length()]; //给table第一行赋值,意思是S[0]中有多少个T[0~j] //显然,S[0]最多包含一个T[0],故table[0][1~n]都为0 if (S.charAt(0) == T.charAt(0)) { table[0][0] = 1; } for (int i = 1; i < S.length(); i++) { char s = S.charAt(i); //给table[i][0]赋值,意思是S[0~i]中有多少个T[0] if (s == T.charAt(0)) { table[i][0] = table[i - 1][0] + 1; } else { table[i][0] = table[i - 1][0]; } for (int j = 1; j < T.length(); j++) { char t = T.charAt(j); if (s == t) { //如果用S[i]匹配T[j],那么S[0~i-1]敏感词有table[i-1][j-1]个T[0~j-1] //如果不用S[i]匹配T[i],那么S[0~i]敏感词有table[i-1][j]个T[0~j] table[i][j] = table[i - 1][j - 1] + table[i - 1][j]; } else { //S[i]!=T[j]时,S[0~i]敏感词有table[i-1][j]个T[0~j] table[i][j] = table[i - 1][j]; } } } return table[S.length() - 1][T.length() - 1]; } }
public int numDistinct(String s, String t) { if(s==null||t==null) return 0; int[][] res=new int[t.length()+1][s.length()+1]; for(int i=0;i<=s.length();i++){ res[0][i]=1; } for(int i=0;i<t.length();i++){ for(int j=0;j<s.length();j++){ if(t.charAt(i)==s.charAt(j)) res[i+1][j+1]=res[i][j]+res[i+1][j]; else res[i+1][j+1]=res[i+1][j]; } } return res[t.length()][s.length()]; }
// 关键在于弄清楚对退公式与状态矩阵 // dp[i][j] 表示 S中的前i个字符构成的字符串包含 T 中前j个字符构成的字符串的 子串的个数 // 当S【i-1】 == t【j-1】时, 则新的dp值可以是 不使用第i个字符,却能构成T中j子串的个数dp[i][j] 加上 // 不使用第i个字符能构成T中j-1子串的个数dp[i-1][j-1] // 否则,只能是等于dp[i-1][j] class Solution { public: int numDistinct(string S, string T) { int slen = S.length(); int tlen = T.length(); vector<vector<int>> dp; vector<int> temp(tlen+1,0); temp[0] = 1; for( int i = 0; i <= slen; i++) dp.push_back( temp ); for( int i = 1; i <= slen ; i++) for(int j = 1 ; j <= tlen ; 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[slen][tlen]; } };
class Solution { public: int numDistinct(string S, string T) { int l = T.length(); vector<int> result(l+1); result[0] = 1; for(int i=1;i<=S.length();i++) for(int j=min(i,l);j>0;j--) { if(S[i-1] == T[j-1]) result[j] = result[j] + result[j-1]; } return result[l]; } };
我们需要一个二维数组dp(i)(j)来记录长度为i的字串在长度为j的母串中出现的次数,这里长度都是从头算起的,而且遍历时,保持子串长度相同,先递增母串长度,母串最长时再增加一点子串长度重头开始计算母串。
首先我们先要初始化矩阵,当子串长度为0时,所有次数都是1,当母串长度为0时,所有次数都是0.当母串子串都是0长度时,次数是1(因为都是空,相等)。接着,如果子串的最后一个字母和母串的最后一个字母不同,说明新加的母串字母没有产生新的可能性,可以沿用该子串在较短母串的出现次数,所以dp(i)(j) = dp(i)(j-1)。如果子串的最后一个字母和母串的最后一个字母相同,说明新加的母串字母带来了新的可能性,我们不仅算上dp(i)(j-1),也要算上新的可能性。那么如何计算新的可能性呢,其实就是在既没有最后这个母串字母也没有最后这个子串字母时,子串出现的次数,我们相当于为所有这些可能性都添加一个新的可能。所以,这时dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。下图是以rabbbit和rabbit为例的矩阵示意图。计算元素值时,当末尾字母一样,实际上是左方数字加左上方数字,当不一样时,就是左方的数字。
class Solution { public: int numDistinct(string S, string T) { // write code here int lens = S.length(); int lent = T.length(); vector<vector<int>> dp(lens+1,vector<int>(lent+1)); //第一行设置为0 第一列设置为1 dp[0][0] = 1; for(int i=1;i<=lens;++i) { dp[i][0]=1; for(int j=1;j<=lent;++j) { if(S[i-1]==T[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; else dp[i][j] = dp[i-1][j]; } } return dp[lens][lent]; } };