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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
