這是leetcode第115道題目，題目大概：Given a string S and a string T, count the number of distinct subsequences of S which equals T.給一個字符串S和字符串T，計算出S的子字符串是T的數量，舉一個例子：
Example 1:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation: 看下面，有三種方式可以生成“rabbit”
解法：
一開始我就想到用動態規劃，比如abbc，abc
a b b c
a | true false false false
b | false true true false
c | false false false true
從true來看，倒過來來看，這樣1*2*1=2
再比如abcbc，abc
a b c b c
a | true false false false false
b | false true false true false
c | false false true false true
1*1*1 + 1*2*1=3
這樣的話我們寫出實現代碼：
class Solution {
public static int numDistinct(String s, String t) {
boolean distinctNums = new boolean[t.length][s.length];
for(int i = 0; i < t.length; i++) {
for(int j = 0; j < s.length; j++) {
if(s.charAt(j) == t.charAt(i)) {
distinctNums[i][j] = true;
}
}
}
return calcNum(distinctNums, distinctNums.length - 1, distinctNums[0].length - 1);
}
private static int calcNum(boolean distinctNums, int m, int n) {
if(m < 0) {
return 1;
}
int num = 0;
for(int j = n; j >= 0 ; j--) {
if(distinctNums[m][j]==true)
num += calcNum(distinctNums, m - 1, j - 1);
}
return num;
}
}
但是這樣實現之後我們發現性能很差，需要轉換一下思路，
if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+dp[i+1][j]
if(s[i]!=t[j]) dp[i+1][j+1]=dp[i+1][j]
實現代碼：
class Solution {
public static int numDistinct(String s, String t) {
int distinctNums = new int[t.length + 1][s.length + 1];
for (int j = 0; j <= s.length; j++) {
distinctNums[0][j] = 1;
}
return calcNum(distinctNums, s, t);
}
private static int calcNum(int distinctNums, String s, String t) {
for (int i = 0; i < t.length; i++) {
for (int j = 0; j < s.length; j++) {
if (t.charAt(i) == s.charAt(j)) {
distinctNums[i + 1][j + 1] = distinctNums[i][j] + distinctNums[i + 1][j];
} else {
distinctNums[i + 1][j + 1] = distinctNums[i + 1][j];
}
}
}
return distinctNums[t.length][s.length];
}
}
閱讀更多 v心之所向v 的文章
