难度: Medium
原题连接
内容描述
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?
思路 1 - 时间复杂度: O(len(s)+len(t))- 空间复杂度: O(1)******
最naive的思路是递归，原来可以beats 53.74%
但是今天上来发现多了case，超时过不了了
时间复杂度为O(len(s)+len(t))
class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if s == '':
return True
for i in range(len(t)):
if t[i] == s[0]:
return self.isSubsequence(s[1:],t[i+1:])
return False
思路 2 - 时间复杂度: O(max(len(s), len(t)))- 空间复杂度: O(1)******
因为递归操作以及对字符串的操作太过于昂贵，所以用index来处理，节省了时间和空间
时间复杂度是O(max(len(s), len(t)))
beats 40%
class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if s == '':
return True
ps, pt = 0, 0
while ps < len(s) and pt < len(t):
if s[ps] == t[pt]:
ps += 1
pt += 1
return ps >= len(s)思路 3 - 时间复杂度: O(len(t))- 空间复杂度: O(1)******
想到说对于每一个s中的字符，看看在不在，找到了就记录一下t的当前位置idx，下次从t的idx+1后面开始找
class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
idx = 0
for c in s:
idx = t.find(c, idx)
if idx == -1:
return False
idx += 1
return TrueIf 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?
思路 1 - 时间复杂度: O(lt+kmsO(lg(lt)))- 空间复杂度: O(lt)****
我们可以先把t里面的所有字符和其出现的idx的list分别作为key和value放进一个字典里面
然后对于s中的每个字符，我们要做两步判断：
- 如果这个字符不在字典里面，直接返回False
- 如果这个字符在字典里面，那我们就看看我们在这个字符在t里面出现的idx的list里面是不是有比上一个字符的idx更大的idx，
例如对于输入
"abc"
"ahbgdc"
首先初始化idx为-1
lookup = {'a': [0], 'c': [5], 'b': [2], 'd': [4], 'g': [3], 'h': [1]}
我们先找字符a，发现a在lookup里面的list为[0]，并且里面存在比idx -1更大的元素，所以我们找到了字符a，更新 idx为1，意味着下一个字符要从t的idx 1开始找
开始找字符b，发现b在lookup里面的list为[2]，并且里面存在比idx 1更大的元素，所以我们找到了字符b，更新idx 为3，意味着下一个字符要从t的idx 3开始找
开始找字符c，发现c在lookup里面的list为[5]，并且里面存在比idx 3更大的元素，所以我们找到了字符c，更新idx 为6，意味着下一个字符要从t的idx 6开始找
但是此时所有字符都已经找到，直接返回True
假设t的长度为lt，s的长度为ls,一共有k个s（假设最长的一个s长度为ms）
我们只需要最开始对整个t做一个遍历，时间复杂度为O(lt)，同时用了一个字典，空间复杂度为O(lt)，
然后对于每一个s的每一个字符，我们都只需要进行一个二分查找，时间复杂度为O(lg(lt))，因为最坏有可能t只有一个字符，它在字典里面对应的list的长度就是lt
因此最终的时间复杂度为O(lt+kmsO(lg(lt)))，时间复杂度为O(lt)
class Solution(object):
def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
lookup = {}
for i in range(len(t)):
if t[i] in lookup:
lookup[t[i]].append(i)
else:
lookup[t[i]] = [i]
idx = -1
for c in s:
if c not in lookup:
return False
else:
c_idx = bisect.bisect_left(lookup[c], idx)
if c_idx == len(lookup[c]): # this means we don't find next char of s in t
return False
idx = lookup[c][c_idx] + 1 # we have to find next char from the prev char's index + 1
return True