题目描述
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
解题思想
代码
/*
类似 最长公共子序列
dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。
递推公式
if (s[i - 1] == t[j - 1]),那么dp[i][j] = dp[i - 1][j - 1] + 1;,
因为找到了一个相同的字符,相同子序列长度自然要在dp[i-1][j-1]的基础上加1(如果不理解,在回看一下dp[i][j]的定义)
if (s[i - 1] != t[j - 1]),此时相当于t要删除元素,t如果把当前元素t[j - 1]删除,
那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了,即:dp[i][j] = dp[i][j - 1];
和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的,区别就是 本题 如果删元素一定是字符串t,
而 1143.最长公共子序列 是两个字符串都可以删元素。
*/
class Solution {
public:
bool isSubsequence(string s, string t) {
if (s.size() > t.size()) return false;
vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
//不同的地方
else dp[i][j] = dp[i][j - 1];
}
}
if (dp[s.size()][t.size()] == s.size()) return true;
return false;
}
};