題目
leetcode唬格， 392. 判斷子序列
給定字符串 s 和 t 字币，判斷 s 是否為 t 的子序列。
你可以認(rèn)為 s 和 t 中僅包含英文小寫字母。字符串 t 可能會(huì)很長(zhǎng)（長(zhǎng)度 ~= 500,000），而 s 是個(gè)短字符串（長(zhǎng)度 <=100）。
字符串的一個(gè)子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對(duì)位置形成的新字符串浦夷。（例如辖试，"ace"是"abcde"的一個(gè)子序列，而"aec"不是）劈狐。
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
后續(xù)挑戰(zhàn) :
如果有大量輸入的 S罐孝，稱作S1, S2, ... , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列肥缔。在這種情況下莲兢，你會(huì)怎樣改變代碼？
分解子問題
假設(shè)s長(zhǎng)度是n续膳，s是t的子序列的前提條件是前n-1個(gè)字符串也是t的子序列改艇；
假設(shè)前n-1個(gè)子序列最后一個(gè)字符在t的位置是j，那么只要第n個(gè)字符串在j之后存在坟岔，那么就可以得到s也是t的子序列
定義遞推關(guān)系
定義f(n) 返回值為is_sub和end_index谒兄，is_sub表示為s的前n個(gè)字符是否是t的子序列，end_index表示第n個(gè)字符在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])
自底向上實(shí)現(xià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;
}
};
