標簽：#雙指針 #字符串 #動態規劃

Ⅰ. 題目

給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。

• 進階：
  如果有大量輸入的 S，稱作 S1, S2, … , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會怎樣改變代碼？

Ⅱ. 示例

· 示例 1：
輸入：s = “abc”, t = “ahbgdc”
輸出：true

· 示例 2：
輸入：s = “axc”, t = “ahbgdc”
輸出：false

0. 個人方法

遍歷字符串 t，逐個和 s 字符串對比，如果相同就讓cnt++（我的代碼里寫的是 position），不同就繼續遍歷字符串 t，如果 cnt == s.length()，那么就說明字符串 t 中有字符串 s 這個子序列

class Solution {
public:bool isSubsequence(string s, string t) {if (t.length() < s.length())return false;if (t.length() == 0 && s.length() == 0)return true;int position = 0;for (int i=0; i<t.length(); ++i){if (t[i] == s[position]){position++;}if (position == s.length()){return true;}}return false;}
};

官方題解一：雙指針

大致思路與個人方法相同

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.length(), m = t.length();int i = 0, j = 0;while (i < n && j < m) {if (s[i] == t[j]) {i++;}j++;}return i == n;}
};

官方題解二：動態規劃

（如果需要多次查詢 s 是否是 t 的子序列，DP方法更高效）

考慮到前面雙指針的做法，我們注意到我們有大量的時間用于在 t 中找到下一個匹配字符。
因此，我們可以考慮對 t 進行預處理，記錄從當前位置起，往后每一個字符第一次出現的位置。

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.size(), m = t.size();// DP 表：f[i][j] 表示 t 從位置 i 開始，字符 j 第一次出現的位置vector<vector<int>> f(m + 1, vector<int>(26, 0));// 初始化邊界：如果 t 的末尾之后的位置，所有字符都不可達（設為 m）for (int j = 0; j < 26; j++) {f[m][j] = m;}// 填充 DP 表for (int i = m - 1; i >= 0; i--) {for (int j = 0; j < 26; j++) {if (t[i] == j + 'a')  // 當前字符匹配f[i][j] = i;else                  // 否則繼承 i+1 的結果f[i][j] = f[i + 1][j];}}// 遍歷 s，檢查是否能在 t 中找到匹配的字符int add = 0;  // 當前在 t 中的查找起始位置for (int i = 0; i < n; i++) {if (f[add][s[i] - 'a'] == m) {  // 字符 s[i] 在 t 中不存在return false;}add = f[add][s[i] - 'a'] + 1;  // 跳到匹配位置的下一個位置}return true;  // 所有字符都匹配成功}
};

• 示例1：

  • 輸入：s = “abc”, t = “ahbgdc”

    • 預處理 t 后，f 會記錄每個字符的位置。

    • 匹配 s：

      • ‘a’ 在 t 的位置 0 → add = 1

      • ‘b’ 在 t 的位置 2 → add = 3

      • ‘c’ 在 t 的位置 5 → 匹配成功

  • 輸出：true

• 示例2:

  • 輸入：s = “axc”, t = “ahbgdc”

    • ‘a’ 匹配 t[0] → add = 1

    • ‘x’ 在 t 中不存在 → 返回 false