摘要
- 套用“最長公共子序列”的思路，LeetCode392 判斷子序列可以轉(zhuǎn)化為：求s和t的最長公共子序列的長度，并判斷這個最長公共子序列的長度是否和s的長度相等。
- LeetCode115 不同的子序列的dp數(shù)組的初始化非常重要，要回顧dp數(shù)組的定義，正確的進(jìn)行初始化。
- 長度為0的字符串、dp數(shù)組的下標(biāo)為0等情況要仔細(xì)考慮。
LeetCode392 判斷子序列
雙指針
- 不考慮動態(tài)規(guī)劃的話，這道題目可以使用雙指針法簡單地解決。
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();
}
};
時間復(fù)雜度為 ，至少要遍歷一次
t。
空間復(fù)雜度為 ，只需要維護(hù)快慢兩個指針的位置。
為了便于對比，將使用動態(tài)規(guī)劃思路的題解代碼也在這里放一份。
動態(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();
}
};
時間復(fù)雜度為 ，與
s和t的size有關(guān)，兩層循環(huán)。
空間復(fù)雜度為 ，需要維護(hù)一個二維的
dp數(shù)組?？梢杂脻L動數(shù)組優(yōu)化到 。
這道題目可以看成“編輯距離”類型的題目的入門題目，只需要考慮從
t中刪除元素來得到s，不需要考慮增加或替換元素。實際上，如果套用“最長公共子序列”的思路，這道題目就可以轉(zhuǎn)化為：求
s和t的最長公共子序列的長度，并判斷這個最長公共子序列的長度是否和s的長度相等。dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i][j]表示，s的子序列中的元素的下標(biāo)屬于[0, i-1]，t的子序列中的元素的下標(biāo)屬于[0, j-1]，這兩個子序列相等時的最長長度為dp[i][j]。-
遞推公式，
dp[i][j]的更新有兩種可能- 如果
s[i - 1] == t[j - 1]，說明當(dāng)前比對到的字符可以接在已知的公共子序列后，根據(jù)dp數(shù)組的定義，新增字符前的最長公共子序列的長度為dp[i - 1][j - 1]，公共子序列新增字符s[i - 1]（t[j - 1]），則長度+1， - 如果
s[i - 1] != t[j - 1]，說明需要從t中刪除t[j - 1]來得到s（不一定要真正的刪除，只是模擬刪除的過程），相當(dāng)于不選取t[j - 1]進(jìn)入最長公共子序列，那么根據(jù)dp數(shù)組的定義，比對過了t[j - 1]而不選取，相當(dāng)于已知的公共子序列不變，
- 如果
初始化
dp數(shù)組，dp[i][0]和dp[0][j]都應(yīng)該初始化成0，相當(dā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();
}
};
- 這道題目，只需要知道在主序列（較長的序列
t）中是否存在子序列s，不需要知道存在多少個子序列s，不需要知道有多少種從主序列中刪除元素的方法能夠得到s。所以只需要比對長度。下一題就需要求出有多少種從主序列中刪除元素的方法能夠得到子序列，比較復(fù)雜。
以s = "abc", t = "ahbgdc"為例，模擬dp數(shù)組的更新過程。
LeetCode115 不同的子序列
這道題目和上一道題類似，但是 LeetCode 給出的難度分類一下子從簡單變成了困難。
dp數(shù)組不能是最長公共子序列的長度了，只保存長度的信息是不夠的，dp數(shù)組應(yīng)該保存從主序列中選出目標(biāo)子序列的方法種數(shù)。dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i][j]表示的是，從主序列s中嘗試選出一個子序列，其中元素的下標(biāo)屬于[0, i-1]，從目標(biāo)序列t中嘗試選出一個子序列，其中元素的下標(biāo)屬于[0, j-1]，使得這兩個子序列相等的選取方法的種數(shù)。-
遞推公式，
dp[i][j]有兩種更新的可能- 如果
s[i - 1] == t[j - 1]，說明可以選取s[i - 1]，- 但是不一定選取
s[i - 1]，因為在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] - 那么，比對完
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ù)組時，除了要保證初始值不會阻礙遞推公式更新dp數(shù)組以外，也要回顧dp數(shù)組的定義。- 先看
dp[0][j]，根據(jù)dp數(shù)組的定義，主序列s的長度是0，即主序列s中沒有任何元素，沒有任何元素可以選取，當(dāng)然無法選取出一個子序列和目標(biāo)序列t相等，所以dp[0][j]=0 - 再看
dp[i][0]，根據(jù)dp數(shù)組的定義，主序列s的長度是i，但是目標(biāo)序列t的長度是0即目標(biāo)序列t是空序列，所以在主序列s中選取0個元素就可以得到目標(biāo)序列t，選取0個元素也就是不選取任何元素，方法種數(shù)是1。所以dp[i][0]=1 - 那
dp[0][0]初始化成0還是1呢？還是看dp數(shù)組的定義，主序列s的長度是0，沒有任何元素可以選取，但是目標(biāo)序列t的長度也是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ù)組的更新過程
