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.
后续挑战 :
如果有大量输入的 S，称作S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
1、两个游标，遍历一遍
- 代码
// java
class Solution {
public boolean isSubsequence(String s, String t) {
if (s == null || s.length() == 0) {
return true;
}
int i_s = 0,i_t = 0;
while(i_s < s.length() && i_t < t.length()) {
if(s.charAt(i_s) == t.charAt(i_t)) {
i_s++;
}
i_t++;
}
return i_s == s.length();
}
}
2、利用String类的indexOf方法
// Java
class Solution {
public boolean isSubsequence(String s,String t) {
int index = -1;
for (char c : s.toCharArray()) {
// 求出c在字符串t中从index开始第一次出现的位置，并重新赋值给index
index = t.indexOf(c,index+1);
// 没找到提前结束
if (index == -1) {
return false;
}
}
// 查找完毕
return ture;
}
}
3、二维动态规划
$dp[i][j]$ 表示s[i]于t[j]是否匹配
// c++
bool isSubsequence(string s, string t) {
vector<vector<int>> d(2,vector<int>(t.size()+1,0));
for(int i=0;i<=s.size();++i){
for(int j=0;j<=t.size();++j){
if(i == 0 && j == 0){
d[i&1][j] = 1;
}else if(i == 0 && j > 0){
d[i&1][j] = 1;
}else if(i > 0 && j == 0){
d[i&1][j] = 0;
}else{
if(s[i-1] == t[j-1]){
d[i&1][j] = d[(i-1)&1][j-1] && 1;
}else{
d[i&1][j] = d[i&1][j-1];
}
}
}
}
return d[s.size()&1][t.size()];
}
// 作者：jason-2
// 链接：https://leetcode-cn.com/problems/is-subsequence/solution/san-chong-jie-fa-by-jason-2-11/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
对于扩展问题的思考
可以先预处理字符串t,将查找每一个字符串s的件复杂度降低到 $O(s.length())$
那么怎么预处理力呢？那肯定是用空间换时间了！！
可以通过预处理的结果，直接根据一个线索字符的位置，常数时间内查找到后面一个目标字符的最近位置。
这种类似对同一个长字符串做很多次匹配的 ，可以像KMP算法一样，先用一些时间将长字符串中的数据提取出来，磨刀不误砍柴功。有了提取好的数据，就可以快速的进行匹配。
空间复杂度 O(t.length() * 26),对于每一个字符，hash其之后的26个英文字符的位置。
int[][] dp = new int[t.length()+1][26];
public class Solution{
int[][] hash;
String t;
public void init(){
hash = new int[t.length()+1][26];
// 初始化hash数组
t = " "+ t;
char[] charT = t.toCharArray();
for (int c = 'a',c <= 'z';c++) {
int index = -1;
for (int i = charT.length - 1;i>=0;i--) {
hash[i][c - 'a'] = index;
if (charT[index] == c){
index = i;
}
}
}
}
public boolean search(String s){
int i = 0;
for(char c : s.toCharArray()) {
i = hash[i][c-'a'];
// 后续不存在c,查找结束
if (i == -1){
return false;
}
}
return ture;
}
public boolean isSubsequence(String s, String t) {
this.t = t;
init();
return search(s);
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
