题目
leetcode， 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 的子序列。在这种情况下，你会怎样改变代码？
分解子问题
假设s长度是n，s是t的子序列的前提条件是前n-1个字符串也是t的子序列；
假设前n-1个子序列最后一个字符在t的位置是j，那么只要第n个字符串在j之后存在，那么就可以得到s也是t的子序列
定义递推关系
定义f(n) 返回值为is_sub和end_index，is_sub表示为s的前n个字符是否是t的子序列，end_index表示第n个字符在t的位置
has(begin_index, c) 返回字符c是否在t的以begin_index开始的后面字符串里。
is_sub, end_index = f(n-1)
f(n) = is_sub && has(end_index + 1, s[n])
自底向上实现
class Solution {
public:
bool isSubsequence(string s, string t) {
int end_index;
return isSubsequence((char*)s.c_str(), s.size(), (char*)t.c_str(), t.size(),end_index);
}
bool isSubsequence(char* s, int s_len, char* t, int t_len, int& end_index){
if(s_len==0){
return true;
}
int last_end_index = -1;
if(isSubsequence(s, s_len-1, t, t_len, last_end_index)){
if(has(t, t_len, last_end_index+1, s[s_len-1], last_end_index)){
end_index = last_end_index;
return true;
}else{
return false;
}
}else{
return false;
}
}
bool has(char* t, int t_len, int offset, char c, int &end_index){
if(t_len <= offset){
return false;
}
end_index = offset;
char t_c = t[end_index];
while(t_c){
if(t_c == c){
return true;
}
end_index++;
t_c = t[end_index];
}
return false;
}
};
