LeetCode:Distinct Subsequences
2100 ワード
Distinct Subsequences
Total Accepted: 51556
Total Submissions: 177996
Difficulty: Hard
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,
Here is an example: S =
Return
Subscribe to see which companies asked this question
Hide Tags
Dynamic Programming String
SからTへの可能な変換を求める.
考え方:ゲージ
設定:S=“rabbit”,T=“rabbit”
dp[T.length()+1][S.length()+1];
手動計算:
j 0 1 2 3 4 5 6 7
i S r a b b b i t
0 T 1 1 1 1 1 1 1 1
1 r 0 1 1 1 1 1 1 1
2 a 0 0 1 1 1 1 1 1
3 b 0 0 0 1 2 3 3 3
4 b 0 0 0 0 1 3 3 3
5 i 0 0 0 0 0 0 3 3
6 t 0 0 0 0 0 0 0 3
結果は、3(=dp[T.length()][S.length()]);
上記のdpテーブルの横線部分の数字を観察すると、生成プロセスは次のようになります.
if(T[i] == S[j]) dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
else dp[i][j] = dp[i][j-1];
次のようになります.
T[i]==S[j]の場合、現在の文字は保持しても捨ててもよい.
T[i]!=S[j]の場合、現在の文字は捨てるしかありません.
i=0の場合、Tが空であることを示す場合、S中のすべての文字を削除する変換は1つしかありません.
java code:
Total Accepted: 51556
Total Submissions: 177996
Difficulty: Hard
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
. Subscribe to see which companies asked this question
Hide Tags
Dynamic Programming String
SからTへの可能な変換を求める.
考え方:ゲージ
設定:S=“rabbit”,T=“rabbit”
dp[T.length()+1][S.length()+1];
手動計算:
j 0 1 2 3 4 5 6 7
i S r a b b b i t
0 T 1 1 1 1 1 1 1 1
1 r 0 1 1 1 1 1 1 1
2 a 0 0 1 1 1 1 1 1
3 b 0 0 0 1 2 3 3 3
4 b 0 0 0 0 1 3 3 3
5 i 0 0 0 0 0 0 3 3
6 t 0 0 0 0 0 0 0 3
結果は、3(=dp[T.length()][S.length()]);
上記のdpテーブルの横線部分の数字を観察すると、生成プロセスは次のようになります.
if(T[i] == S[j]) dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
else dp[i][j] = dp[i][j-1];
次のようになります.
T[i]==S[j]の場合、現在の文字は保持しても捨ててもよい.
T[i]!=S[j]の場合、現在の文字は捨てるしかありません.
i=0の場合、Tが空であることを示す場合、S中のすべての文字を削除する変換は1つしかありません.
java code:
public class Solution {
public int numDistinct(String s, String t) {
int m = t.length();
int n = s.length();
int[][] dp = new int[m+1][n+1];
for(int i=0;i<=m;i++) dp[i][0] = 0;
for(int j=0;j<=n;j++) dp[0][j] = 1;
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
if(s.charAt(j-1)==t.charAt(i-1))
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
else
dp[i][j] = dp[i][j-1];
}
}
return dp[m][n];
}
}