判断子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序> > 列,而"aec"不是)。
示例 1:
输入:s = "abc", t = "ahbgdc" 输出:true 示例 2:
输入:s = "axc", t = "ahbgdc"
输出:false
提示:
0 <= s.length <= 100 0 <= t.length <= 10^4 两个字符串都只由小写字符组成。
方法一:双指针
本题询问的是,
假定当前需要匹配字符
,而字符 在 中的位置 和 出现 ,那么贪心取 是最优解,因为 后面能取到的字符,也都能取到,并且通过 与 之 间的可选字符,更有希望能匹配成功。
这样,我们初始化两个指针
class Solution {
public boolean isSubsequence(String s, String t) {
int n = s.length(), m = t.length();
int i = 0, j = 0;
while (i < n && j < m) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == n;
}
}
复杂度分析
- 时间复杂度:
,其中 为 的长度, 为 的长度。每次无论是匹配成功还是失败,都有至少一个指针发生右移,两指针能够位移的总距离为 。 - 空间复杂度:
。
方法二:动态规划
考虑前面的双指针的做法,我们注意到我们有大量的时间用于在
这样我们可以预处理出对于
我们可以使用动态规划的方法实现预处理,令
这样我们可以写出状态转移方程:
假定下标从
这样,我们可以利用
同时我们注意到,该解法中对
的处理与 无关,且预处理完成后,可以利用预处理数组的信息,线性地算出任意一个字符串 是否为 的子串。这样我们就可以解决「后续挑战」啦。
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;
}
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];
}
}
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;
}
}
复杂度分析
- 时间复杂度:
,其中 为 的长度, 为 的长度, 为字符集,在本题中字符串只包含小写字母, 。预处理时间复杂度 ,判断子序列时 间复杂度 。 - 如果是计算
个平均长度为 的字符串是否为 的子序列,则时间复杂度为 。
- 如果是计算
- 空间复杂度:
。