題目鏈接：392. 判斷子序列

題目描述

給定字符串?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 <= s.length <= 100
• 0 <= t.length <= 10^4
• 兩個字符串都只由小寫字符組成。

文章講解：代碼隨想錄

視頻講解：動態(tài)規(guī)劃，用相似思路解決復(fù)雜問題 | LeetCode：392.判斷子序列_嗶哩嗶哩_bilibili

題解1：動態(tài)規(guī)劃

思路：使用動態(tài)規(guī)劃法求解子序列問題，本題判斷 s 和 t 的最長公共子序列長度是否為 s 的長度。

動態(tài)規(guī)劃分析：

• dp 數(shù)組以及下標的含義：dp[i][j] 表示以 s[i] 結(jié)尾和 t[j] 結(jié)尾的最長公共子序列長度。
• 遞推公式：當?s[i - 1] 等于 t[j - 1] 時，dp[i][j] = dp[i - 1][j - 1] + 1；否則，dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])。
• dp 數(shù)組初始化：全部初始化為0。
• 遍歷順序：從上往下，從左往右。
• ?打印 dp 數(shù)組：以輸入 s?= "abc"、t?= "ahbgdc" 為例，dp 數(shù)組為 [ [ 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 1, 1, 1, 1, 1 ], [ 0, 1, 1, 2, 2, 2, 2 ], [ 0, 1, 1, 2, 2, 2, 3 ] ]。

/*** @param {string} s* @param {string} t* @return {boolean}*/
var isSubsequence = function(s, t) {const dp = new Array(s.length + 1).fill().map(() => new Array(t.length + 1).fill(0));for (let i = 1; i <= s.length; i++) {for (let j = 1; j <= t.length; j++) {if (s[i - 1] === t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[s.length][t.length] === s.length;
};

分析：時間復(fù)雜度為 O(m * n)，空間復(fù)雜度為 O(m * n)。

題解2：雙指針

思路：

/*** @param {string} s* @param {string} t* @return {boolean}*/
var isSubsequence = function(s, t) {let index = 0;for (let i = 0; i < t.length; i++) {if (t[i] === s[index]) {index++;}}return index === s.length;
};

分析：時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。

收獲

練習使用動態(tài)規(guī)劃法求解子序列問題。