LeetCode: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，總共有幾種不同的刪除方法
設S的長度為lens，T的長度為lent
算法1 ：遞歸解法，首先，從個字符串S的尾部開始掃描，找到第一個和T最后一個字符相同的位置k，那么有下面兩種匹配：a. T的最后一個字符和S[k]匹配，b. T的最后一個字符不和S[k]匹配。a相當于子問題:從S[0...lens-2]中刪除幾個字符得到T[0...lent-2]，b相當于子問題：從S[0...lens-2]中刪除幾個字符得到T[0...lent-1]。那么總的刪除方法等于a、b兩種情況的刪除方法的和。遞歸解法代碼如下，但是通過大數據會超時：
1
class
Solution {
2
public
:
3
int
numDistinct(
string
S,
string
T) {
4
//
IMPORTANT: Please reset any member data you declared, as
5
//
the same Solution instance will be reused for each test case.
6
return
numDistanceRecur(S, S.length()-
1
, T, T.length()-
1
);
7
}
8
int
numDistanceRecur(
string
&S,
int
send,
string
&T,
int
tend)
9
{
10
if
(tend <
0
)
return
1
;
11
else
if
(send <
0
)
return
0
;
12
while
(send >=
0
&& S[send] != T[tend])send--
;
13
if
(send <
0
)
return
0
;
14
return
numDistanceRecur(S,send-
1
,T,tend-
1
) + numDistanceRecur(S,send-
1
,T,tend);
15
}
16
};
算法2 ：動態規劃，設dp[i][j]是從字符串S[0...i]中刪除幾個字符得到字符串T[0...j]的不同的刪除方法種類，有上面遞歸的分析可知，動態規劃方程如下
- 如果S[i] = T[j], dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
- 如果S[i] 不等于 T[j], dp[i][j] = dp[i-1][j]
- 初始條件：當T為空字符串時，從任意的S刪除幾個字符得到T的方法為1
代碼如下： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 本文地址
1
class
Solution {
2
public
:
3
int
numDistinct(
string
S,
string
T) {
4
//
IMPORTANT: Please reset any member data you declared, as
5
//
the same Solution instance will be reused for each test case.
6
int
lens = S.length(), lent =
T.length();
7
if
(lent ==
0
)
return
1
;
8
else
if
(lens ==
0
)
return
0
;
9
int
dp[lens+
1
][lent+
1
];
10
memset(dp,
0
,
sizeof
(dp));
11
for
(
int
i =
0
; i <= lens; i++)dp[i][
0
] =
1
;
12
for
(
int
i =
1
; i <= lens; i++
)
13
{
14
for
(
int
j =
1
; j <= lent; j++
)
15
{
16
if
(S[i-
1
] == T[j-
1
])
17
dp[i][j] = dp[i-
1
][j-
1
]+dp[i-
1
][j];
18
else
dp[i][j] = dp[i-
1
][j];
19
}
20
}
21
return
dp[lens][lent];
22
}
23
};
【版權聲明】轉載請注明出處： http://www.cnblogs.com/TenosDoIt/p/3440022.html
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
