从前往后顺序遍历 t,查看它是否跟 s[i] 相等,如果相等则 i++ 。
如果 i 增加到了 s 末尾,说明匹配完成
如果 t 先遍历结束,说明匹配不完成
复杂度是 O(n) (n 是t 的长度,在最糟糕的情况要把 t 遍历完)
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(s) == 0: return True
i = 0
for x in t:
if x == s[i]:
i += 1
if i == len(s):
return True
return False
解法二
遍历 s 要快很多
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(s) == 0: return True
i = 0
for x in s:
i = t.find(x, i)
if i == -1:
return False
else:
i += 1
return True
https://leetcode-cn.com/problems/is-subsequence/
解法一
从前往后顺序遍历 t,查看它是否跟 s[i] 相等,如果相等则 i++ 。 如果 i 增加到了 s 末尾,说明匹配完成 如果 t 先遍历结束,说明匹配不完成
复杂度是 O(n) (n 是t 的长度,在最糟糕的情况要把 t 遍历完)
解法二
遍历 s 要快很多