echo

任生命穿梭 时间的角落

0%

判断子序列

392. 判断子序列

给定字符串 st ,判断 s 是否为 t 的子序列。

你可以认为 st 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace""abcde"的一个子序列,而"aec"不是)。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

最直观的办法就是维护两个指针,判断子序列中的所有字符是否在原始字符串中。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean isSubsequence(String s, String t) {
int i=0, j=0;
for(;i<t.length() && j<s.length();++i){
if(t.charAt(i) == s.charAt(j)){
++j;
}
}
//子字符串被全部匹配
return j == s.length();
}
}

时间复杂度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],我们从后往前进行动态规划,得到状态转移方程:
f[i][j]=i,   t[i]=j

f[i][j]=f[i+1][j],   t[i]j

假设下标从 0 开始,那么 f[i][j]中有 0 <= i <= m - 1,对于边界条件 f[m - 1][...],我们置 f[m][...] = m,让f[m - 1][...]进行正常转移。

我们利用 f 数组,每次O(1)地跳转到下一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public boolean isSubsequence(String s, String t) {
int n = s.length(), m = t.length();
int[][] f = new int[m + 1][26];
//边界条件
for(int i = 0; i < 26; i++){
f[m][i] = m;
}
//生成 dp 数组
for(int i = m - 1; i >= 0; i--){
for(int j = 0; j < 26; j++){
if(t.charAt(i) == j + 'a')
f[i][j] = i;
else
f[i][j] = f[i + 1][j];
}
}
//从头部开始查看 s 是是 t 的子序列
int add = 0;
for(int i = 0; i < n; i++){
if(f[add][s.charAt(i) - 'a'] == m){
return false;
}
add = f[add][s.charAt(i) - 'a'] + 1;
}

return true;
}
}

时间复杂度O(m * 26 + n),其中 n 为 s 的长度,m 为 t 的长度。

空间复杂度O(m * 26)。

Powered By Valine
v1.5.2