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

Leetcode 392 判断子序列

news 2025/7/5 19:25:57

题意理解：

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

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

即判断s和t是否存在一个最长公共子序列，且该最长公共子序列==s

这里采用一个动态规划的思路求解最长公共子序列，其长度==s.size

解题思路：

(1) 定义dp数组

定义二维dp数组，dp[i][j]表示s第i个元素前，t第j个元素前最长公共子序列。

i，j指示的是元素之间的位置

其i属于[0,s.size+1], j属于[0,t.size+1]

（2）初始化

dp[0][j]和dp[i][0]表示第一行第一列，其都是用一个空数组和一个非空数组求其最长公共给子序列，所以全部初始化为0.

其余元素初始化为0，后续操作会被覆盖掉。

（3）递推公式

if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1

else dp[i][j]=max(dp[i][j-1]，dp[i-1][j])

(4)返回

if(dp[s.size-1][t.size-1]==s.size) return true;

else return false;

1.动态规划

public boolean isSubsequence(String s, String t) {int[][] dp=new int[s.length()+1][t.length()+1];for(int i=0;i<s.length();i++){Arrays.fill(dp[i],0);}for(int i=1;i<=s.length();i++){for(int j=1;j<=t.length();j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}if(dp[s.length()][t.length()]==s.length()) return true;return false;}