LeetCode392. 判断子序列

思路

1.定义dp数组

dp[i][j]:表示s中到下标为i-1的字符串和t中到下标为t-1的字符串中相同的子字符串的长度为dp[i][j].

注：为什么是i-1和j-1是为了在定义递推公式的时候方便，如果定义为i和j的话就会很麻烦。之前就有字符串问题时定义为i-1的。

2.递推公式

如果s中i-1的字符和t中j-1的字符相等，则dp[i][j] = dp[i-1][j-1]+1;

为什么是i-1和j-1呢？请看dp数组的定义。

如果不等的话dp[i][j] = dp[i][j-1];就相当于，获得到下标为j-2和小标为i-1的字符串的值。

为什么不是 dp[i][j] = dp[i-1][j-1]呢？

因为i-1和j-1的字符不相等，说明i-1处的字符没有在当前以j-1结束的字符串中，那dp[i][j] = dp[i][j-1]。如果是dp[i][j] = dp[i-1][j-1]的话，那就是下标以i-2结尾的s和下标以j-2结尾的t的值。就漏掉了下标为i-1的字符。将会计算错误。

3.初始化

根据dp数组的定义就可以知道dp[i][0] = 0;dp[0][j] = 0;

4.遍历顺序

根据递推公式，应该是正序遍历。

5.打印dp数组

dp数组的最后的一个元素的值和s的长度一样就是true否则就是false。

代码

class Solution {    public boolean isSubsequence(String s, String t) { int l1 = s.length(); int l2 = t.length(); int dp[][] = new int[l1+1][l2+1];  for(int i = 1;i<=l1;i++){     for(int j = 1;j<=l2;j++){  if(s.charAt(i-1) == t.charAt(j-1)){      dp[i][j] = dp[i-1][j-1] + 1;  }else{      dp[i][j] = dp[i][j-1];  }     } } if(dp[l1][l2] == l1){     return true; }else{     return false; }    }}