寫在前面

本專欄專注于分析與講解【面試經(jīng)典150】算法，兩到三天更新一篇文章，歡迎催更……

專欄內(nèi)容以分析題目為主，并附帶一些對(duì)于本題涉及到的數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行回顧與總結(jié)，文章結(jié)構(gòu)大致如下，部分內(nèi)容會(huì)有增刪：

• Tag：介紹本題牽涉到的知識(shí)點(diǎn)、數(shù)據(jù)結(jié)構(gòu)；
• 題目來源：貼上題目的鏈接，方便大家查找題目并完成練習(xí)；
• 題目解讀：復(fù)述題目（確保自己真的理解題目意思），并強(qiáng)調(diào)一些題目重點(diǎn)信息；
• 解題思路：介紹一些解題思路，每種解題思路包括思路講解、實(shí)現(xiàn)代碼以及復(fù)雜度分析；
• 知識(shí)回憶：針對(duì)今天介紹的題目中的重點(diǎn)內(nèi)容、數(shù)據(jù)結(jié)構(gòu)進(jìn)行回顧總結(jié)。

Tag

【雙指針】【動(dòng)態(tài)規(guī)劃】【字符串】

---

題目來源

392. 判斷子序列

---

題目解題

判斷字符串 s 是不是字符串 t 的子序列，字符串的子序列指的是原字符串刪除一些字符或者不刪除字符但是不改變?cè)瓉碜址樞蚨纬傻男碌淖址?/p>

---

解題思路

方法一：雙指針

我們使用兩個(gè)指針 i 和 j，初始化分別指向字符串 s 和 t 的初始位置。從前往后對(duì) s[i] 和 t[j] 進(jìn)行匹配：

• 如果 s[i] = t[j]，則同時(shí)向右移動(dòng)雙指針；
• 如果 s[i] != t[j]，則只移動(dòng)指向字符串字符的指針 j；
• 無論是否匹配，都需要移動(dòng) j 指針；
• 最終，如果 i 移動(dòng)到了字符串 s 的末尾，說明 s 是 t 的子序列。

實(shí)現(xiàn)代碼

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

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(n+m)$，$n$ 為 s 的長(zhǎng)度，$m$ 為 t 的長(zhǎng)度。無論匹配是否成功，都至少youyige有一個(gè)指針向右移動(dòng)，兩指針的移動(dòng)總距離為 $n+m$。

空間復(fù)雜度：$O(1)$，僅僅使用了兩個(gè)指針變量。

方法二：動(dòng)態(tài)規(guī)劃

方法一有可以進(jìn)行優(yōu)化的地方，在方法一中，我們需要枚舉匹配 t 中的字符，如果 t 中不匹配的字符很長(zhǎng)，我們會(huì)有大量的時(shí)間浪費(fèi)在 t 中找下一個(gè)匹配的字符。

于是，我們可以先對(duì)字符串 t 進(jìn)行預(yù)處理，記錄從每個(gè)位置開始往后每一個(gè)字符第一次出現(xiàn)的位置。

狀態(tài)

f[i][j] 表示字符串 t 中從位置 i 開始往后字符 j 第一次出現(xiàn)的位置。

狀態(tài)轉(zhuǎn)移

有如下的狀態(tài)轉(zhuǎn)移關(guān)系：

• 如果 t[i] = j，那么 f[i][j] = i；
• 否則，f[i][j] = f[i+1][j]。

根據(jù)以上轉(zhuǎn)移關(guān)系，我們需要對(duì)字符串 t 從后往前進(jìn)行動(dòng)態(tài)規(guī)劃。

base case

我們的邊界狀態(tài)為 f[m-1][...]，我們置 f[m][...] = m，讓 f[m-1][...] 正常轉(zhuǎn)移，如果 f[i][j] = m，則表示從位置 i 開始往后不存在字符 j。

我們通過 f 數(shù)組，可以快速定位到字符串 t 后面每一個(gè)第一次出現(xiàn)的字符（s 中的字符）：

• 如果 f[i][j] = m，則表示從字符串 t 位置 i 開始往后不存在 s 中的字符 j，則直接返回 false；
• 否則，更新 i，從新的位置開始定位 s 中的字符；
• 如果一直沒遇到 m，最后返回 true。

方法二使用動(dòng)態(tài)規(guī)劃的方法對(duì)字符串 t 進(jìn)行一次處理，可以大大提高匹配，也是 進(jìn)階 題目的一種解法。

實(shí)現(xiàn)代碼

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.size(), m = t.size();vector<vector<int>> f(m+1, vector<int>(26, 0));for (int i = 0; i < 26; ++i) {f[m][i] = m;}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 f[i][j] = f[i+1][j];}}int start = 0;for (int i = 0; i < n; ++i) {if (f[start][s[i] - 'a'] == m)return false;start = f[start][s[i] - 'a'] + 1;}return true;}
};  

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(m\times \left|\sum \right|+n)$，$n$ 為字符串 s 的長(zhǎng)度，m 為字符串 t 的長(zhǎng)度，$\left|\sum \right|$ 為字符集，$\left|\sum \right|=26$。

空間復(fù)雜度：$O(m\times \left|\sum \right|)$，使用的額外空間為對(duì)字符串 t 預(yù)處理所占用的空間。

---

寫在最后

如果文章內(nèi)容有任何錯(cuò)誤或者您對(duì)文章有任何疑問，歡迎私信博主或者在評(píng)論區(qū)指出 💬💬💬。

如果大家有更優(yōu)的時(shí)間、空間復(fù)雜度方法，歡迎評(píng)論區(qū)交流。

最后，感謝您的閱讀，如果感到有所收獲的話可以給博主點(diǎn)一個(gè) 👍 哦。