392. 判断子序列
给定字符串 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
.
最直观的办法就是维护两个指针,判断子序列中的所有字符是否在原始字符串中。
1 | class Solution { |
时间复杂度O(n),空间复杂度O(1)。
双指针解法中有大量的时间用于在 t 中找到下一个匹配字符。我们预处理出对于 t 的每一个位置,从该位置开始往后的每种字符第一次出现的位置。
令f[i][j]
表示字符串 t 从位置 i 开始往后字符 j 第一次出现的位置。在进行状态转移时,如果 t 中位置 i 的字符就是 j ,那么f[i][j] = i
,否则 j 出现在位置 i + 1开始往后,即f[i][j] = f[i + 1][j]
,我们从后往前进行动态规划,得到状态转移方程:
假设下标从 0 开始,那么 f[i][j]
中有 0 <= i <= m - 1,对于边界条件 f[m - 1][...]
,我们置 f[m][...] = m
,让f[m - 1][...]
进行正常转移。
我们利用 f 数组,每次O(1)地跳转到下一个位置。
1 | class Solution { |
时间复杂度O(m * 26 + n),其中 n 为 s 的长度,m 为 t 的长度。
空间复杂度O(m * 26)。
v1.5.2