当前位置：首页 > ops >正文

代码随想录|动态规划|47判断子序列

ops 2025/7/13 1:22:56

leetcode:392. 判断子序列 - 力扣（LeetCode）

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

0 <= s.length <= 100
0 <= t.length <= 10^4

两个字符串都只由小写字符组成

思路

动归五部曲

（1）dp数组定义

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

（2）递推公式

考虑两种情况：

if (s[i - 1] == t[j - 1])
- t中找到了一个字符在s中也出现了
if (s[i - 1] != t[j - 1])
- 相当于t要删除元素，继续匹配

如果s[i - 1] == t[j - 1]，那么这两段子序列最后一个字符相同，同时去掉最后这个字符，然后再找公共子序列长度，最后+1。

如果s[i - 1] ≠ t[j - 1]，这里的分析参考 “最长公共子序列”里面说的：

当时写的是 max(dp[i - 1][j], dp[i][j - 1])

但是这里已经说明了t的长度要比s更长，所以只写dp[i][j - 1]就行。

后面的就是一样的，全部参考代码随想录|动态规划|44最长公共子序列-CSDN博客

只是这道题要看的是s是不是t的子序列，意思就是：

s和t的最长公共子序列长度 = s的长度

说明s就是t的子序列。

代码：

class Solution
{
public:bool isSubsequence(string s, string t){int m=s.size(),n=t.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for(int i=1;i<=m;i++){for(int j=1;j<=n;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[m][n] == m)return true;elsereturn false;}
};