共计 2172 个字符,预计需要花费 6 分钟才能阅读完成。
392. 判断子序列
题目起源:https://leetcode-cn.com/problems/is-subsequence/
题目
给定字符串 s 和 t,判断 s 是否为 t 的子序列。
你能够认为 s 和 t 中仅蕴含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也能够不删除)字符而不扭转残余字符绝对地位造成的新字符串。(例如,”ace” 是 ”abcde” 的一个子序列,而 ”aec” 不是)。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
后续挑战 :
如果有大量输出的 S,称作 S1, S2, … , Sk 其中 k >= 10 亿,你须要顺次查看它们是否为 T 的子序列。在这种状况下,你会怎么扭转代码?
解题思路
思路:双指针、动静布局
在这里,先理清题目所提出的问题,题目要问的是,s 是否是 t 的子序列?而题目中定义这个子序列,是指不扭转绝对地位在原字符串中删除一些(或者不删除)字符残余的字符。
那么也就是说,只有能找到 s 在 t 中存在(绝对地位程序对应),那么能够认定 s 是 t 的子序列。例如,题目中所给出的示例,”ace” 是 “abcde” 的一个子序列,而 “aec” 不是。因为 “aec” 扭转了绝对地位的程序。
在这里,咱们能够从前往后匹配,而且可贪婪地靠前匹配呈现的字符。
当咱们从前往后匹配字符的时候,假如呈现的字符 x 在 t 中呈现的地位,一个在后面,一个在前面。在这里,应该思考匹配 x 在 t 呈现后面的字符,这是因为往后匹配,入选定后面地位呈现的字符时,可能更大概率匹配胜利。(因为字符 x 呈现在前面地位往后能取的字符,后面地位往后也可能取到,而且前后两个地位之前的字符也有可选字符。)
那么具体的算法如下:
- 定义双指针 p、q,别离指向 s 和 t 的初始地位;
- 这里匹配后面地位呈现的字符(也就是进行贪婪匹配),当匹配胜利之后,指针同时往后挪动;
- 如果匹配失败,p 放弃不同,挪动 q。
- 如果 p 可能达到开端,那么阐明 s 就是 t 的子序列。
具体的代码见【代码实现 # 双指针】
还有一个后续挑战,须要测验大量的 s 是否是 t 的子序列。在下面的双指针的办法当中,从前往后去匹配字符须要大量的工夫,那么这里再应用双指针的办法显然不适合。
这里参考官网题解,说一下动静布局如何去疾速匹配 s 是否是 t 的子序列。
首先用动静布局的办法去进行预处理,可能确定在 t 的每个地位,从该地位往后每个字符第一次呈现的地位。
状态定义
设 dpi 示意字符串 t 中从 i 的地位开始往后匹配,j 第一次呈现的地位。
状态转移方程
- 如果 t 中地位 i 的字符就是 j 的话,那么 dpi = i;
- 若不是下面的状况,那么也就是说 j 呈现在 i 地位之后的某个地位(这里不蕴含 i),此时 dpi = dpi+1
状态初始化
在这里,索引从 0 开始,那么 i 的取值范畴为 0, t_len),这里不蕴含 t_len。那么,这里存在边界问题,当 i = t_len-1 的时候,这里可能会无奈进行转移。咱们让 i = t_len 的时候,令 dp[t_len 为 t_len,那么也就说,当 dpi = t_len 的时候,那么就示意从 i 开始无奈匹配 j。
具体的代码见【代码实现 # 动静布局】
代码实现
# 双指针
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
s_len = len(s)
t_len = len(t)
# 定义双指针,指向 s 和 t 的初始地位
p = 0
q = 0
while p < s_len and q < t_len:
# 当 s 的字符与 t 的字符匹配时
# 同时挪动 p 和 q 指针
if s[p] == t[q]:
p += 1
# 如果不匹配,只挪动 q 指针,与 p 指针所对应的字符持续匹配判断
q += 1
# 如果 p 指针达到 s 开端返回 True
return p == s_len
# 动静布局
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
s_len = len(s)
t_len = len(t)
dp = [[0] * 26 for _ in range(t_len)]
# 这里是为了可能让 i = t_len-1 的时候可能失常转移
dp.append([t_len]*26)
# 在这里,从后往前枚举,因为 dp[i][j] 可能从 dp[i+1][j] 中转移而来
for i in range(t_len-1, -1, -1):
for j in range(26):
# 如果地位 i 的字符就是 j 时,那么 dp[i][j] = i
if ord(t[i]) == j + ord('a'):
dp[i][j] = i
else:
dp[i][j] = dp[i+1][j]
# dp[i][j] = i if ord(t[i]) == j + ord('a') else dp[i+1][j]
# 开始遍历匹配 s,测验 s 的每个字符在 t 中的某个地位是否存在
idx = 0
for i in range(s_len):
# 如果转移只有后果为 t_len,示意无奈匹配字符,那么返回 False
if dp[idx][ord(s[i]) - ord('a')] == t_len:
return False
# 当找到匹配以后字符的地位之后,从这个地位的下一个地位开始查找下一个字符是否呈现在 t 中的某个地位
idx = dp[idx][ord(s[i]) - ord('a')] + 1
return True
实现后果
双指针
动静布局
欢送关注
公众号【书所集录】