1. question: 判断子序列（简单）
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/is-subsequence
示例 1：
1
2
| 输入：s = "abc", t = "ahbgdc"
输出：true
|
示例 2：
1
2
| 输入：s = "axc", t = "ahbgdc"
输出：false
|
提示：
1
2
3
| 0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
|
2. answers
这道题判断s是否是t的子序列，我最开始想的是求解s和t的最长公共子序列，如果子序列的长度和s相等，那么就说明s是t的子序列。代码如下所示：
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| public class Solution_0141 {
public boolean isSubsequence(String s, String t) {
if(s.length() == 0) return true;
if(t.length() == 0) return false;
int[][] dp = new int[s.length()][t.length()];
if(s.charAt(0) == t.charAt(0)) dp[0][0] = 1;
else dp[0][0] = 0;
for (int i = 1; i < s.length(); i++) {
if(s.charAt(i) == t.charAt(0))
dp[i][0] = 1;
else dp[i][0] = dp[i-1][0];
}
for (int i = 1; i < t.length(); i++) {
if(t.charAt(i) == s.charAt(0))
dp[0][i] = 1;
else dp[0][i] = dp[0][i-1];
}
for (int i = 1; i < s.length(); i++) {
for (int j = 1; j < t.length(); j++) {
if(s.charAt(i) == t.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[s.length() - 1][t.length() - 1] == s.length();
}
public static void main(String[] args) {
System.out.println();
Solution_0141 s0141 = new Solution_0141();
String s = "axc";
String t = "ahbgdc";
System.out.println(s0141.isSubsequence(s, t));
}
}
|
参考了题解，可利用双指针法。一个指针遍历s，另一个指针遍历t。当二者元素相等时，都向后移动一位；当不等时，t指针向后移动。最终如果s遍历完，那么就说明s是t的子序列，否则则不是。代码如下所示：
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
35
36
37
38
39
| public class Solution_0141_02 {
public boolean isSubsequence(String s, String t) {
int m = s.length();
int n = t.length();
int i = 0;
int j = 0;
while(i < m && j < n) {
if(s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == m;
}
public static void main(String[] args) {
System.out.println();
Solution_0141_02 s0141 = new Solution_0141_02();
String s = "axc";
String t = "ahbgdc";
System.out.println(s0141.isSubsequence(s, t));
}
}
|
其实以双指针的思想来看，就是判断是否在t中逐个发现s中每个字符。那么以这种思路来看，可改进一下上面动态规划的实现。
上面动态规划，本质上是找两个字符串的最长公共子序列，然后判断是否和s字符串相等。其实没有必要这样做，可以在遍历的时候，就直接按照t中是否存在该字符来做。这样，依然定义dp[i][j]表示s[i]和t[j]两个子串所形成的最长公共序列，但是状态方程如下：
- 如果s[i]==t[j]，显然dp[i][j]=dp[i-1][j-1]+1
- 如果s[i]!=t[j]，此时的结果只能是dp[i][j-1]，相当于删除t中本元素，考虑前面的结果，因为本题是以s为标准，即只能从t中删除元素。
代码如下所示：
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| public class Solution_0141_03 {
public boolean isSubsequence(String s, String t) {
if(s.length() == 0) return true;
if(t.length() == 0) return false;
int[][] dp = new int[s.length()][t.length()];
if(s.charAt(0) == t.charAt(0)) dp[0][0] = 1;
else dp[0][0] = 0;
for (int i = 1; i < t.length(); i++) {
if(s.charAt(0) == t.charAt(i)) dp[0][i] = 1;
else dp[0][i] = dp[0][i-1];
}
for (int i = 1; i < s.length(); i++) {
dp[i][0] = 0;
}
for (int i = 1; i < s.length(); i++) {
for (int j = 1; j < t.length(); j++) {
if(s.charAt(i) == t.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = dp[i][j-1];
}
}
return dp[s.length() - 1][t.length() - 1] == s.length();
}
public static void main(String[] args) {
System.out.println();
Solution_0141_03 s0141 = new Solution_0141_03();
String s = "abc";
String t = "ahbgdc";
System.out.println(s0141.isSubsequence(s, t));
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
