【力扣题】题目描述：
【Python3】代码：
1、解题思路：遍历字符串s，使用一个列表依次记录在字符串t中的位置，若没有该字母则返回False，若索引号小于上一个字母的索引号，返回False。否则返回True。
知识点：[ ]：创建新列表。相当于 list()。
字符串.find(...)：在字符串中查找某元素，返回索引号，没有返回-1。
列表[-1]：获取列表中最后一个元素。
列表.append(...)：往列表尾部添加一个元素。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
alist = []
i = -1
for x in s:
i = t.find(x,i+1)
if i == -1: return False
if alist and i <= alist[-1]:
return False
alist.append(i)
return True
也可以用两个队列分别记录字符串s和t，遍历字符串s，依次从t的队列队头移除一个元素，若与s的字母相同，s的队列队头移除该元素，最终s的队列没有元素，则返回True，否则返回False。
知识点：collections.deque(...)：双端队列。左端进，右端出。也可以右端进，左端出。
队列.popleft()：从队列的队头（左端）移除一个元素，并返回该元素。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
from collections import deque
sdeque, tdeque = deque(s), deque(t)
for x in s:
while tdeque:
if x == tdeque.popleft():
sdeque.popleft()
break
return not sdeque
也可以遍历字符串t，依次判断是否与字符串s中的字母相同。若字符串t遍历完，字符串s仍有字母，则返回False，否则返回True。
知识点：字符串[索引]：获取字符串中索引号对应的元素。
字符串[起始索引 : 结束索引]：获取字符串中起始索引（含）到结束索引（不含）的元素。
len(...)：获取序列的长度。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
for x in t:
if s and x == s[0]:
s = s[1:]
return not s
# 或者
i, n = 0, len(s)
for x in t:
if i < n and x == s[i]:
i += 1
return i == n
2、解题思路：双指针。两个指针分别指向两个字符串的起始位置，比对两字母是否相同，若相同，同时指向下一个，若不同，只有字符串t的指针指向下一个。若字符串t遍历完，字符串s仍有字母，则返回False，否则返回True。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i, j = 0, 0
n, m = len(s), len(t)
while i < n and j < m:
if t[j] == s[i]:
i += 1
j += 1
return i == n
3、解题思路：动态规划。
① 获取字符串t的长度m，一个m+1行26列的矩阵（最后一行的内容都为m）。
② 1行对应字符串t的1个元素，26列依次对应26个字母。从后往前遍历字符串t，每一个字母对应的位置记录其在字符串t中的索引号，该行其他列等于下一行该列的内容（例如：字符串t第2个元素为c，则矩阵中行号为1列号为2中内容为1，该行其他列为下一行的内容，注意索引号从0开始）。
③ 遍历字符串s，第一个字母从第一行开始找，字母对应位置中内容若为m，则字符串t中不存在该字母返回False，若不为m，则该位置中内容+1作为下一个字母查找的行号，全部查找完，则返回True。
知识点：ord(...)：将字符转为ASCII或者Unicode数值。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
m = len(t)
f = [[0] * 26 for i in range(m)]
f.append([m] * 26)
for i in range(m-1,-1,-1):
for j in range(26):
f[i][j] = i if j == ord(t[i]) - ord("a") else f[i+1][j]
add = 0
for x in s:
index = ord(x) - ord("a")
if f[add][index] == m: return False
add = f[add][index] + 1
return True
4、解题思路：迭代器。将字符串t转为迭代器，遍历字符串s，所有字母都在该迭代器中则返回True，否则返回False。
知识点：iter(...)：转为迭代器。迭代器中元素只依次访问一次。
all(...)：所有都满足条件，则返回True，否则返回False。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
a = iter(t)
return all(x in a for x in s)
5、解题思路：使用正则表达式查找。
知识点：".*".join(s)：相当于将字符串s中每个内容中间添加.*。例如：
re.search(...)：使用正则表达式查找某字符串，其中正则表达式".*" 匹配0个或多个任意字符（除了换行符\n）。
__import__(...)：动态加载类和函数。如果一个模块经常变化就可以使用 __import__() 来动态载入。
bool(...)：转为布尔类型，只有True和False。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
return bool(__import__("re").search(".*".join(s), t))
# 或者
import re
res = re.search(".*".join(s), t)
return bool(res)
参考文章
您阅读本篇文章共花了：
发表评论