GuilinDev
Lc0392
05 August 2008
392 Is Subsequence
题目
Given a string s and a string t, check if s is subsequence of t.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, 1
"ace"
Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
Example 1:
1
2
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
1
2
Input: s = "axc", t = "ahbgdc"
Output: false
Constraints:
- 0 <= s.length <= 100
- 0 <= t.length <= 10^4
- Both strings consists only of lowercase characters.
分析
1）双指针
假定当前需要匹配字符 c，而字符 c 在 t 中的位置以 x1 和 x2出现（x1 < x2 ），那么贪心取x 1 是最优解，因为 x2 后面能取到的字符，x1 也都能取到，并且通过x1 与 x2 之间的可选字符，更有希望能匹配成功
2）考虑前面的双指针的做法，可以注意到有大量的时间用于在 t 中找到下一个匹配字符。可以预处理出对于 t 的每一个位置，从该位置开始往后每一个字符第一次出现的位置。这样，就不用花时间逐个寻找下一个字符在后面与否。
可以使用动态规划的方法实现预处理：
状态定义- 令 f[i][j] 表示字符串 t 中从位置 i 开始往后字符 j 第一次出现的位置。
初始化 - n为较短s的长度，m为较长t的长度；假定下标从0开始，那么 f[i][j]中有0≤i≤m−1 ，对于边界状态 f[m-1][..]，我们置 f[m][..] 为 m，让 f[m-1][..] 正常进行转移。这样对于某个字符j，如果 f[i][j]=m，则表示从位置 i 开始往后不存在字符 j。
状态转移方程 - 在进行状态转移时，如果 t 中位置 i 的字符就是 j，那么 f[i][j]=i，否则 j 出现在位置 i+1 开始往后，即 f[i][j]=f[i+1][j]，因此要倒过来进行动态规划，从后往前枚举 i。
这样我们可以写出状态转移方程：
这样，我们可以利用一个数组来记录（空间换时间），每次花费 O(1) 时间就可以跳转到下一个位置（而不需要一个个对比字符寻找），直到位置变为 m 或 s 中的每一个字符都匹配成功。
考虑状态压缩 - 同时注意到，该解法中对 t 的处理与 s 无关，且预处理完成后，可以利用预处理数组的信息，线性地算出任意一个字符串 s 是否为 t 的子串。这样可以解决follow up问题，“如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？”
3) Binary Search也可以解决输入大量字符串的问题。
代码
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public boolean isSubsequence(String s, String t) {
if (s.isEmpty()) {
return true;
}
if (t.isEmpty()) {
return false;
}
int indexS = 0;
int indexT = 0;
while (indexS < s.length() && indexT < t.length()) {
if (s.charAt(indexS) == t.charAt(indexT)) {
indexS++;
indexT++;
} else {
indexT++;
}
}
return indexS == s.length();
}
}
DP
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
30
31
32
33
34
class Solution {
public boolean isSubsequence(String s, String t) {
int n = s.length(), m = t.length();
// 二维数组记录在t中每个位置，26个小写字母在当前或者之后出现的位置
// m + 1表示额外在最后多出来一个记录表示不存在
int[][] dp = new int[m + 1][26];
for (int i = 0; i < 26; i++) { // 在最后一个位置上初始化所有26个小写字母的位置为m(不存在)
dp[m][i] = m;
}
// 从后向前计算t中每个位置对应的26个小写字母的位置
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) {
if (j + 'a' == t.charAt(i)) { //循环查找26个小写字符是否等于从后向前过程中t中的当前字符
dp[i][j] = i;
} else { // 当前字符不等于就让当前等于右边的状态
dp[i][j] = dp[i + 1][j];
}
}
}
// 开始查找s是否为t的子串
int add = 0; // 记录s中下一个字符的位置
for (int k = 0; k < n; k++) {
int index = s.charAt(k) - 'a';
if (dp[add][index] == m) { // 到了最右没找完s中字符
return false;
}
add = dp[add][index] + 1;
}
return true;
}
}