Q：给定字符串 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.
A：
双指针
public boolean isSubsequence(String s, String t) {
if (s.length() == 0)
return true;
if (t.length() == 0 || t.length() < s.length())
return false;
int indexs = 0;
int indext = 0;
while (indexs < s.length() && indext < t.length()) {
if (s.charAt(indexs) == t.charAt(indext)) {
indexs++;
}
indext++;
}
return indexs == s.length();
}
还有一个利用java本身的函数的，特别方便：java中String类有这样一个方法public int indexOf(int ch, int fromIndex) ，他表示的是在字符串中是否存在一个字符ch，并且是从字符串的下标fromIndex开始查找的。我们要做的是在t字符串中查找s中的每一个字符，如果没查到，直接返回false。如果查到，就从t的下一个位置继续开始查
public boolean isSubsequence(String s, String t) {
int index = -1;
for (char c : s.toCharArray()) {
//index表示上一次查找的位置(第一次查找的时候为-1)，所以这里要从t的下标(index+1)开始查找
index = t.indexOf(c, index + 1);
//没找到，返回false
if (index == -1)
return false;
}
return true;
}
后续挑战 :
如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
引用：对后续挑战的一些思考--如何快速判断大量字符串
我们前期多做一点工作，将长字符串研究透彻，假如长字符串的长度为 nn，建立一个 n * 26n∗26 大小的矩阵，表示每个位置上26个字符下一次出现的位置，对于要匹配的短字符串，遍历每一个字符，不断地寻找该字符在长字符串中的位置，然后将位置更新，寻找下一个字符，相当于在长字符串上“跳跃”。如果下一个位置为 -1，表示长字符串再没有该字符了，返回 false 即可。
public boolean isSubsequence(String s, String t) {
//考虑到 对第一个字符的处理 ，在t 之前一个空字符
t=' '+t;
//对t长字符串 做预处理
int[][] dp = new int[t.length()][26];//存储每一个位置上 a--z的下一个字符出现的位置
for (char c = 'a'; c <= 'z'; c++) {//依次对每个字符作处理
int nextPos = -1;//表示接下来不会在出现该字符
for (int i = t.length() - 1; i >= 0; i--) {//从最后一位开始处理
dp[i][c - 'a'] = nextPos;//dp[i][c-'a'] 加上外层循环 就是对每一个位置的a---z字符的处理了
if (t.charAt(i) == c) {//表示当前位置有该字符 那么指向下一个该字符出现的位置就要被更新为i
nextPos = i;
}
}
}
//数据的利用 ，开始匹配
int index=0;
for (char c:s.toCharArray()){
index=dp[index][c-'a'];//因为加了' '，所以之后在处理第一个字符的时候 如果是在第一行，就会去第一行，不影响之后字符的判断
if(index==-1){
return false;
}
}
return true;
}