31 lines
881 B
JavaScript
31 lines
881 B
JavaScript
/**
|
||
* @param {string} s
|
||
* @param {string} t
|
||
* @return {boolean}
|
||
*/
|
||
const isSubsequence = function (s, t) {
|
||
return f1(s, t);
|
||
};
|
||
|
||
/*
|
||
这个题目起始从头到尾遍历开s[1]在不在t中，然后再看s[2]在不在，最后看s[len - 1]在不在，如果在则返回true,
|
||
这个题目也可以是使用动态规划，动态规划的思路就是，如果s[i]在t中存在，如果s[i+1:]这个子序列也在t中存在,
|
||
那么s[i:]开始的子序列，在t中也存在，定义dp[i]为，字符串s从i开始的所有子序列s[i:]在t[j]之后的子序列中存在
|
||
s[i] === t[j]
|
||
*/
|
||
function f2(s, t) {
|
||
if (s.length === 0) return true;
|
||
if (t.length === 0) return false;
|
||
|
||
const dp = Array(s.length).fill(false);
|
||
|
||
for (let j = t.length - 1, i = s.length - 1; j >= 0 && i >= 0; j--) {
|
||
if (t[j] === s[i]) {
|
||
dp[i] = true;
|
||
i--;
|
||
}
|
||
}
|
||
|
||
return dp[0];
|
||
}
|