392判断子序列

wangkaixin-yy / 2023-05-05 / 原文

1.初始化动态数组,加边界,所有从t超界的位置找一个字母一定是找不到的,所以设为边界值即代表无穷大。

2.预处理:因为如果t现在位置找不到所找字母则从t后一位开始找,所以

f[i][j]=f[i+1][j]//同时从后往前更新数组(t[i]!=j)
f[i][j]=i//t[i]==j

3.按s的字母顺序查找t

for(int i=0;i<s.length();i++){
    if(f[add][s[i]-'a']==t.length())return false;
    add=f[add][s[i]-'a']+1;//记住要加1,即跳过这个找到的位置从后面开始找
}