Distinct Subsequences

原題鏈接Distinct Subsequences

判斷字符串s中有多少個子序列和t相等，一個字符串的子序列是將字符串中若干字符刪除后形成的字符串

因?yàn)樽有蛄兄凶址捻樞蚴枪潭ǖ?#xff0c;所以不能采用滑動窗(滑動窗常用于解決只要求個數(shù)不要求順序的問題)。

另外，對于源字符串s，假設(shè)其字符個數(shù)為n，對于目標(biāo)字符串t，假設(shè)其字符個數(shù)為m，那么若想要求字符串s中和t[0 : m-1]相等的子序列個數(shù)就需要先求和t[0 : m-2]相等的子序列個數(shù)，又需要先求和t[0 : m-3]相等的子序列個數(shù)…

所以本題可以使用動態(tài)規(guī)劃求解，令dp[i][j]表示字符串s[0 : i-1]中和t[0 : j-1]相等的子序列個數(shù)，最終要求解的是dp[n][m]

另外需要考慮的是，假設(shè)字符串t為空，即m為0，那么dp[i][0]都應(yīng)該為1，因?yàn)橹恍枰獙中所有字符都刪掉即可

求dp[i][j]的方法是

• 如果s[i - 1] == t[j - 1]，說明當(dāng)前位置匹配，那么dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，表示可以認(rèn)為當(dāng)前位置匹配計(jì)算個數(shù)和，也可以不認(rèn)為當(dāng)前位置匹配而在s前面尋找匹配位置
• 如果s[i - 1] != t[j - 1]，那么就老老實(shí)實(shí)的dp[i][j] = dp[i - 1][j]從s前面尋找匹配位置

代碼如下

class Solution { public:int numDistinct(string s, string t) {vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));/* 最重要的是這里，所有迭代的動態(tài)規(guī)劃最不好理解的也都是對dp設(shè)置初值* 由于本題只要t為空，那么可以將s中所有字符刪掉就獲得t，所以可以為1 */for(int i = 0; i <= s.size(); ++i)dp[i][0] = 1;for(int i = 1; i <= s.size(); ++i){for(int j = 1; j <= t.size(); ++j){/* 根據(jù)是否相等執(zhí)行不同操作，因?yàn)榇藭r需要匹配t[0 : j]，而只有相等是才可以允許只匹配t[0 : j-1] */if(s[i - 1] == t[j - 1])dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];elsedp[i][j] = dp[i - 1][j];}}return dp[s.size()][t.size()];} };

---

迭代法最不容易理解的就是對dp設(shè)置初值，其實(shí)設(shè)置初值就是幾個特殊情況，dp[0][j]或者dp[i][0]，弄清楚dp[i][j]表示的含義再進(jìn)行設(shè)置初值比較好

總結(jié)

以上是生活随笔為你收集整理的每天一道LeetCode-----计算字符串s中有多少个子序列和字符串t相等的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。