题目描述
Given a string s and a string t, check if s is subsequence of t.You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace"
is a subsequence of "abcde"
while "aec"
is not).
Example 1:
s = "abc"
, t = "ahbgdc" Return
true`.
Example 2:
s = "axc"
, t = "ahbgdc"
Return false
.
Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
题意:给一个字符串s
和一个字符串t
,判断s
是否是t
的一个子序列。
题解:这题的贪心思路是假设我们用t[j]
匹配了s[i]
,我们匹配s[i + 1]
的时候,需要从j + 1
开始找到第一个t[k] == s[i + 1]
作为当前的匹配。
算法1
(双指针) $O(n + m)$
题解1:双指针做法。使用i
索引当前匹配到s[i]
,j
索引当前匹配到t[j]
。时间复杂度$O(n +m)$
C++ 代码
bool isSubsequence(string s, string t) {
int len1 = s.length(),len2 = t.length(),i = 0 , j = 0;
for(;i < len1 && j < len2 ; i ++,j ++ )
{
while(j < len2 && t[j] != s[i])
j ++;
if(j == len2)
return false;
}
return i == len1;
}
follow up
如果我们k > 1Biillon
个待查询的字符串,如何优化呢?
如果继续使用双指针做法,总的时间复杂度是O(k * (n + m))
的。我们可以先遍历一遍字符串t
,将字符串t
中每个字符出现的位置缓存下来,然后查找s[i]
的时候,只需要在该字母在t
中所有出现的位置进行二分查找就可以了。总的时间复杂度是$O(knlogm)$的。
bool isSubsequence(string s, string t) {
int n = s.length();
int m = t.length();
int cur = -1;
vector<vector<int>> index(26);
for(int i = 0 ; i < m ; i ++)
index[t[i] - 'a'].push_back(i);
for(int i = 0 ; i < n ; i ++)
{
int left = 0 ,right = index[s[i] - 'a'].size();
if(right == 0) return false;
while(left < right)
{
int mid = (left + right) / 2;
if(index[s[i] - 'a'][mid] > cur) right = mid;
else left = mid + 1;
}
if(left >= index[s[i] - 'a'].size() ||index[s[i] - 'a'][left] <= cur)
return false;
else
cur = index[s[i] - 'a'][left];
}
return true;
}
你好 想请问一下下面的
follow up
里面 二分的右边界为什么不是index[s[i] - 'a'].size() -1
呢 下标范围不需要-1呢前面是大于等于呀,如果是大于的话 就需要加上-1