摘要
- 套用“最長(zhǎng)公共子序列”的思路凑兰，LeetCode392 判斷子序列可以轉(zhuǎn)化為：求s和t的最長(zhǎng)公共子序列的長(zhǎng)度，并判斷這個(gè)最長(zhǎng)公共子序列的長(zhǎng)度是否和s的長(zhǎng)度相等遣蚀。
- LeetCode115 不同的子序列的dp數(shù)組的初始化非常重要矾麻，要回顧dp數(shù)組的定義，正確的進(jìn)行初始化芭梯。
- 長(zhǎng)度為0的字符串险耀、dp數(shù)組的下標(biāo)為0等情況要仔細(xì)考慮。
LeetCode392 判斷子序列
雙指針
- 不考慮動(dòng)態(tài)規(guī)劃的話玖喘，這道題目可以使用雙指針法簡(jiǎn)單地解決甩牺。
class Solution {
public:
bool isSubsequence(string s, string t) {
int slow = 0;
for (int fast = 0; fast < t.size(); fast++) {
if (s[slow] == t[fast]) slow++;
if (slow >= s.size()) break;
}
return slow == s.size();
}
};
時(shí)間復(fù)雜度為 ，至少要遍歷一次
t累奈。
空間復(fù)雜度為 贬派，只需要維護(hù)快慢兩個(gè)指針的位置。
為了便于對(duì)比澎媒，將使用動(dòng)態(tài)規(guī)劃思路的題解代碼也在這里放一份搞乏。
動(dòng)態(tài)規(guī)劃
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];
}
}
return dp[s.size()][t.size()] == s.size();
}
};
時(shí)間復(fù)雜度為 ，與
s和t的size有關(guān)戒努，兩層循環(huán)请敦。
空間復(fù)雜度為 ，需要維護(hù)一個(gè)二維的
dp數(shù)組储玫∈躺福可以用滾動(dòng)數(shù)組優(yōu)化到 。
這道題目可以看成“編輯距離”類型的題目的入門題目撒穷，只需要考慮從
t中刪除元素來得到s匣椰，不需要考慮增加或替換元素。實(shí)際上端礼，如果套用“最長(zhǎng)公共子序列”的思路窝爪，這道題目就可以轉(zhuǎn)化為：求
s和t的最長(zhǎng)公共子序列的長(zhǎng)度弛车，并判斷這個(gè)最長(zhǎng)公共子序列的長(zhǎng)度是否和s的長(zhǎng)度相等齐媒。dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i][j]表示蒲每，s的子序列中的元素的下標(biāo)屬于[0, i-1]，t的子序列中的元素的下標(biāo)屬于[0, j-1]喻括，這兩個(gè)子序列相等時(shí)的最長(zhǎng)長(zhǎng)度為dp[i][j]邀杏。-
遞推公式，
dp[i][j]的更新有兩種可能- 如果
s[i - 1] == t[j - 1]唬血，說明當(dāng)前比對(duì)到的字符可以接在已知的公共子序列后望蜡，根據(jù)dp數(shù)組的定義，新增字符前的最長(zhǎng)公共子序列的長(zhǎng)度為dp[i - 1][j - 1]拷恨，公共子序列新增字符s[i - 1]（t[j - 1]）脖律，則長(zhǎng)度+1， - 如果
s[i - 1] != t[j - 1]腕侄，說明需要從t中刪除t[j - 1]來得到s（不一定要真正的刪除小泉，只是模擬刪除的過程），相當(dāng)于不選取t[j - 1]進(jìn)入最長(zhǎng)公共子序列冕杠，那么根據(jù)dp數(shù)組的定義微姊，比對(duì)過了t[j - 1]而不選取，相當(dāng)于已知的公共子序列不變分预，
- 如果
初始化
dp數(shù)組兢交，dp[i][0]和dp[0][j]都應(yīng)該初始化成0，相當(dāng)于沒有比對(duì)任何字符笼痹，任何字符串和空字符串的最長(zhǎng)公共子序列的長(zhǎng)度都是0配喳。遍歷順序，
i和j都是從小到大遍歷凳干。
題解代碼
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];
}
}
return dp[s.size()][t.size()] == s.size();
}
};
- 這道題目晴裹，只需要知道在主序列（較長(zhǎng)的序列
t）中是否存在子序列s，不需要知道存在多少個(gè)子序列s纺座，不需要知道有多少種從主序列中刪除元素的方法能夠得到s息拜。所以只需要比對(duì)長(zhǎng)度。下一題就需要求出有多少種從主序列中刪除元素的方法能夠得到子序列净响，比較復(fù)雜少欺。
以s = "abc", t = "ahbgdc"為例，模擬dp數(shù)組的更新過程馋贤。
LeetCode115 不同的子序列
這道題目和上一道題類似赞别，但是 LeetCode 給出的難度分類一下子從簡(jiǎn)單變成了困難。
dp數(shù)組不能是最長(zhǎng)公共子序列的長(zhǎng)度了配乓，只保存長(zhǎng)度的信息是不夠的仿滔，dp數(shù)組應(yīng)該保存從主序列中選出目標(biāo)子序列的方法種數(shù)惠毁。dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i][j]表示的是，從主序列s中嘗試選出一個(gè)子序列崎页，其中元素的下標(biāo)屬于[0, i-1]鞠绰，從目標(biāo)序列t中嘗試選出一個(gè)子序列，其中元素的下標(biāo)屬于[0, j-1]飒焦，使得這兩個(gè)子序列相等的選取方法的種數(shù)蜈膨。-
遞推公式，
dp[i][j]有兩種更新的可能- 如果
s[i - 1] == t[j - 1]牺荠，說明可以選取s[i - 1]翁巍，- 但是不一定選取
s[i - 1]，因?yàn)樵?code>s[i - 1]前后可能還有s[i - k]或s[i + k]與t[j - 1]相等休雌，所以不一定選取s[i - 1]灶壶，那么嘗試過了s[i - 1]但不選取，保留之前的狀態(tài)杈曲，之前已知的不選取s[i - 1]方法種數(shù)是dp[i - 1][j] - 如果選取
s[i - 1]驰凛，s[i - 1] == t[j - 1]是固定的選取方式，就一種鱼蝉，只要看之前的子序列有多少種相等的可能养涮，之前已知的方法種數(shù)是dp[i - 1][j - 1] - 那么凳鬓，比對(duì)完
s[i - 1]和t[j - 1]之后锥忿，已知選取的方法種數(shù)是以上兩種情況之和
- 但是不一定選取
- 如果
s[i - 1] != t[j - 1]邀摆，說明不可以選取s[i - 1]- 嘗試過了
s[i - 1]但不選取，自然是保留之前的狀態(tài)洁奈，之前能選取出公共子序列但不選取s[i - 1]的方法種數(shù)是dp[i - 1][j]间唉，所以
- 嘗試過了
- 如果
-
初始化
dp數(shù)組，這道題目的dp初始化非常重要利术，初始化dp數(shù)組時(shí)呈野，除了要保證初始值不會(huì)阻礙遞推公式更新dp數(shù)組以外，也要回顧dp數(shù)組的定義印叁。- 先看
dp[0][j]被冒，根據(jù)dp數(shù)組的定義，主序列s的長(zhǎng)度是0轮蜕，即主序列s中沒有任何元素昨悼，沒有任何元素可以選取，當(dāng)然無法選取出一個(gè)子序列和目標(biāo)序列t相等跃洛，所以dp[0][j]=0 - 再看
dp[i][0]率触，根據(jù)dp數(shù)組的定義，主序列s的長(zhǎng)度是i汇竭，但是目標(biāo)序列t的長(zhǎng)度是0即目標(biāo)序列t是空序列葱蝗，所以在主序列s中選取0個(gè)元素就可以得到目標(biāo)序列t穴张，選取0個(gè)元素也就是不選取任何元素，方法種數(shù)是1两曼。所以dp[i][0]=1 - 那
dp[0][0]初始化成0還是1呢皂甘？還是看dp數(shù)組的定義，主序列s的長(zhǎng)度是0合愈，沒有任何元素可以選取叮贩，但是目標(biāo)序列t的長(zhǎng)度也是0，不需要從主序列中選取任何元素即可得到目標(biāo)序列t佛析。所以dp[0][0]=1。
- 先看
遍歷順序：
i彪蓬，j都從小到大遍歷
題解代碼如下
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1, 0));
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++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
else dp[i][j] = dp[i - 1][j];
}
}
return dp[s.size()][t.size()];
}
};
以s = "babgbag", t = "bag"為例寸莫，模擬dp數(shù)組的更新過程
