首页 > 代码库 > LeetCode: Distinct Subsequences 解题报告
LeetCode: Distinct Subsequences 解题报告
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.
SOLUTION 1（AC）:
现在这种DP题目基本都是5分钟AC咯。主页君引一下别人的解释咯：
http://blog.csdn.net/fightforyourdream/article/details/17346385?reload#comments
http://blog.csdn.net/abcbc/article/details/8978146
引自以上的解释：
遇到这种两个串的问题，很容易想到DP。但是这道题的递推关系不明显。可以先尝试做一个二维的表int[][] dp，用来记录匹配子序列的个数（以S ="rabbbit",T = "rabbit"为例）：
r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
从这个表可以看出，无论T的字符与S的字符是否匹配，dp[i][j] = dp[i][j - 1].就是说，假设S已经匹配了j - 1个字符，得到匹配个数为dp[i][j - 1].现在无论S[j]是不是和T[i]匹配，匹配的个数至少是dp[i][j - 1]。除此之外，当S[j]和T[i]相等时，我们可以让S[j]和T[i]匹配，然后让S[j - 1]和T[i - 1]去匹配。所以递推关系为：
dp[0][0] = 1; // T和S都是空串.
dp[0][1 ... S.length() - 1] = 1; // T是空串，S只有一种子序列匹配。
dp[1 ... T.length() - 1][0] = 0; // S是空串，T不是空串，S没有子序列匹配。
dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0).1 <= i <= T.length(), 1 <= j <= S.length()
这道题可以作为两个字符串DP的典型：
两个字符串：
先创建二维数组存放答案，如解法数量。注意二维数组的长度要比原来字符串长度+1，因为要考虑第一个位置是空字符串。
然后考虑dp[i][j]和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]的关系，如何通过判断S.charAt(i)和T.charAt(j)的是否相等来看看如果移除了最后两个字符，能不能把问题转化到子问题。
最后问题的答案就是dp[S.length()][T.length()]
还有就是要注意通过填表来找规律。
注意：循环的时候，一定要注意i的取值要到len，这个出好几次错了。
1 public class Solution { 2 public int numDistinct(String S, String T) { 3 if (S == null || T == null) { 4 return 0; 5 } 6 7 int lenS = S.length(); 8 int lenT = T.length(); 9 10 if (lenS < lenT) {11 return 0;12 }13 14 int[][] D = new int[lenS + 1][lenT + 1];15 16 // BUG 1: forget to use <= instead of <....17 for (int i = 0; i <= lenS; i++) {18 for (int j = 0; j <= lenT; j++) {19 // both are empty.20 if (i == 0 && j == 0) {21 D[i][j] = 1;22 } else if (i == 0) {23 // S is empty, can‘t form a non-empty string.24 D[i][j] = 0;25 } else if (j == 0) {26 // T is empty. S is not empty.27 D[i][j] = 1;28 } else {29 D[i][j] = 0;30 // keep the last character of S.31 if (S.charAt(i - 1) == T.charAt(j - 1)) {32 D[i][j] += D[i - 1][j - 1];33 }34 35 // discard the last character of S.36 D[i][j] += D[i - 1][j];37 }38 }39 }40 41 return D[lenS][lenT];42 }43 }
运行时间：
| Submit Time | Status | Run Time | Language |
|---|---|---|---|
| 13 minutes ago | Accepted | 432 ms | java |
SOLUTION 2:
递归解法也写一下，蛮简单的：
但是这个解法过不了，TLE了。
1 // SOLUTION 2: recursion version. 2 public int numDistinct(String S, String T) { 3 if (S == null || T == null) { 4 return 0; 5 } 6 7 return rec(S, T, 0, 0); 8 } 9 10 public int rec(String S, String T, int indexS, int indexT) {11 int lenS = S.length();12 int lenT = T.length();13 14 // base case:15 if (indexT >= lenT) {16 // T is empty.17 return 1;18 }19 20 if (indexS >= lenS) {21 // S is empty but T is not empty.22 return 0;23 }24 25 int sum = 0;26 // use the first character in S.27 if (S.charAt(indexS) == T.charAt(indexT)) {28 sum += rec(S, T, indexS + 1, indexT + 1);29 }30 31 // Don‘t use the first character in S.32 sum += rec(S, T, indexS + 1, indexT);33 34 return sum;35 }
SOLUTION 3:
递归加上memory记忆之后，StackOverflowError. 可能还是不够优化。确实递归层次太多。
| Runtime Error Message: | Line 125: java.lang.StackOverflowError |
| Last executed input: | "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz |
1 // SOLUTION 3: recursion version with memory. 2 public int numDistinct(String S, String T) { 3 if (S == null || T == null) { 4 return 0; 5 } 6 7 int lenS = S.length(); 8 int lenT = T.length(); 9 10 int[][] memory = new int[lenS + 1][lenT + 1];11 for (int i = 0; i <= lenS; i++) {12 for (int j = 0; j <= lenT; j++) {13 memory[i][j] = -1;14 }15 }16 17 return rec(S, T, 0, 0, memory);18 }19 20 public int rec(String S, String T, int indexS, int indexT, int[][] memory) {21 int lenS = S.length();22 int lenT = T.length();23 24 // base case:25 if (indexT >= lenT) {26 // T is empty.27 return 1;28 }29 30 if (indexS >= lenS) {31 // S is empty but T is not empty.32 return 0;33 }34 35 if (memory[indexS][indexT] != -1) {36 return memory[indexS][indexT];37 }38 39 int sum = 0;40 // use the first character in S.41 if (S.charAt(indexS) == T.charAt(indexT)) {42 sum += rec(S, T, indexS + 1, indexT + 1);43 }44 45 // Don‘t use the first character in S.46 sum += rec(S, T, indexS + 1, indexT);47 48 // record the solution.49 memory[indexS][indexT] = sum;50 return sum;51 }
SOLUTION 4 （AC）:
参考了http://blog.csdn.net/fightforyourdream/article/details/17346385?reload#comments的代码后，发现递归过程找解的过程可以优化。我们不需要沿用DP的思路
而应该与permutation之类差不多，把当前可能可以取的解都去尝试一次。就是在S中找到T的首字母，再进一步递归。
| Submit Time | Status | Run Time | Language |
|---|---|---|---|
| 0 minutes ago | Accepted | 500 ms | java |
1 // SOLUTION 4: improved recursion version 2 public int numDistinct(String S, String T) { 3 if (S == null || T == null) { 4 return 0; 5 } 6 7 int lenS = S.length(); 8 int lenT = T.length(); 9 10 int[][] memory = new int[lenS + 1][lenT + 1];11 for (int i = 0; i <= lenS; i++) {12 for (int j = 0; j <= lenT; j++) {13 memory[i][j] = -1;14 }15 }16 17 return rec4(S, T, 0, 0, memory);18 }19 20 public int rec4(String S, String T, int indexS, int indexT, int[][] memory) {21 int lenS = S.length();22 int lenT = T.length();23 24 // base case:25 if (indexT >= lenT) {26 // T is empty.27 return 1;28 }29 30 if (indexS >= lenS) {31 // S is empty but T is not empty.32 return 0;33 }34 35 if (memory[indexS][indexT] != -1) {36 return memory[indexS][indexT];37 }38 39 int sum = 0;40 for (int i = indexS; i < lenS; i++) {41 // choose which character in S to choose as the first character of T.42 if (S.charAt(i) == T.charAt(indexT)) {43 sum += rec4(S, T, i + 1, indexT + 1, memory);44 }45 }46 47 // record the solution.48 memory[indexS][indexT] = sum;49 return sum;50 }
SOLUTION 5:
在SOLUTION 4的基础之上，把记忆体去掉之后，仍然是TLE
Time Limit ExceededMore Details
| Last executed input: | "daacaedaceacabbaabdccdaaeaebacddadcaeaacadbceaecddecdeedcebcdacdaebccdeebcbdeaccabcecbeeaadbccbaeccbbdaeadecabbbedceaddcdeabbcdaeadcddedddcececbeeabcbecaeadddeddccbdbcdcbceabcacddbbcedebbcaccac", "ceadbaa" |
1 // SOLUTION 5: improved recursion version without memory. 2 public int numDistinct(String S, String T) { 3 if (S == null || T == null) { 4 return 0; 5 } 6 7 return rec5(S, T, 0, 0); 8 } 9 10 public int rec5(String S, String T, int indexS, int indexT) {11 int lenS = S.length();12 int lenT = T.length();13 14 // base case:15 if (indexT >= lenT) {16 // T is empty.17 return 1;18 }19 20 if (indexS >= lenS) {21 // S is empty but T is not empty.22 return 0;23 }24 25 int sum = 0;26 for (int i = indexS; i < lenS; i++) {27 // choose which character in S to choose as the first character of T.28 if (S.charAt(i) == T.charAt(indexT)) {29 sum += rec5(S, T, i + 1, indexT + 1);30 }31 }32 33 return sum;34 }
总结:
大家可以在SOLUTION 1和SOLUTION 4两个选择里用一个就好啦。
http://blog.csdn.net/fightforyourdream/article/details/17346385?reload#comments
这道题可以作为两个字符串DP的典型：
两个字符串：
先创建二维数组存放答案，如解法数量。注意二维数组的长度要比原来字符串长度+1，因为要考虑第一个位置是空字符串。
然后考虑dp[i][j]和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]的关系，如何通过判断S.charAt(i)和T.charAt(j)的是否相等来看看如果移除了最后两个字符，能不能把问题转化到子问题。
最后问题的答案就是dp[S.length()][T.length()]
还有就是要注意通过填表来找规律。
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dp/NumDistinct.java
LeetCode: Distinct Subsequences 解题报告