1. 題目

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

你可以認(rèn)為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會(huì)很長(zhǎng)（長(zhǎng)度 ~= 500,000），而 s 是個(gè)短字符串（長(zhǎng)度 <=100）。

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

示例 1: s = "abc", t = "ahbgdc" 返回 true.示例 2: s = "axc", t = "ahbgdc" 返回 false.

后續(xù)挑戰(zhàn) :
如果有大量輸入的 S，稱作S1, S2, … , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會(huì)怎樣改變代碼？

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/is-subsequence
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 雙指針

• 雙指針?lè)謩e i, j 指向 s， t
• s[i] == t[j] 時(shí)，才 i++

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

2. 二分查找

當(dāng)有大量的字符串s時(shí)，應(yīng)將所有字符的下標(biāo)存進(jìn)表里，進(jìn)行二分查找，提高效率
二分查找參考

class Solution {int L, R, mid; public:bool isSubsequence(string s, string t) {if(s.size() > t.size())return false;vector<vector<int>> m(26);//存儲(chǔ)t中字符對(duì)應(yīng)的位置int i, j = 0;for(i = 0; i < t.size(); ++i){m[t[i]-'a'].push_back(i);//將t對(duì)應(yīng)字符的下標(biāo)存進(jìn)數(shù)組}for(i = 0; i < s.size() && j < t.size(); ++i){j = binarysearch(m[s[i]-'a'], j);//對(duì)s中的字符在對(duì)應(yīng)的t的數(shù)組里，查找大于等于j的位置if(j == -1)//沒(méi)找到，返回錯(cuò)誤return false;j++;//找到了，下次查找開(kāi)始的位置+1}return (i==s.size());}int binarysearch(vector<int>& v, int &pos)//找值>=pos的第一個(gè){L = 0, R = v.size()-1;while(L <= R){mid = L+((R-L)>>1);if(v[mid] >= pos){if(mid==0 || v[mid-1] < pos)return v[mid];elseR = mid-1;}else if(v[mid] < pos)L = mid+1;}return -1;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 392. 判断子序列（双指针二分查找）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。