image.png

    题目解析：对于这类处理两个字符串的问题，我们一般采取两维的dp状态方程。
    我们对状态定义为：dp[i][j]代表s[0, i)和t[0, j)两者的共同子序列长度
    状态初始化，dp[0][...]=0，dp[...][0]=0。
    状态转移，对于这类问题，我们思考的角度是从字符串的最后一个字符，对于字符s[i-1]和t[j-1]，有两种情况：

    • s[i-1]==t[j-1]，那么两者的共同子序列长度+1，即dp[i][j]=dp[i-1][j-1] + 1
    • s[i-1]!=t[j-1]，那么共同子序列的来源只能由s[0,i-1)和t[0,j)或s[0,i)和t[0,j-1)，即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

    于是，我们将原问题判断s是否为t的子序列转化为s和t的共同子序列长度是否等于s的长度。

    • 时间复杂度：O(len1 * len2)。

    • 空间复杂度：O(len1 * len2)。

      1. class Solution {
      2.   public boolean isSubsequence(String s, String t) {
      3.       int len1 = s.length();
      4.       int len2 = t.length();
      5.       int[][] dp = new int[len1 + 1][len2 + 1];
      7.       for(int i = 1; i <= len1; i++){
      8.           for(int j = 1; j <= len2; j++){
      9.               if(s.charAt(i - 1) == t.charAt(j - 1)){
      10.                   dp[i][j] = dp[i - 1][j - 1] + 1;
      11.               }else{
      12.                   dp[i][j] = Math.max(dp[i][j - 1], dp[i-1][j]);
      13.               }
      14.           }
      15.       }
      16.       return dp[len1][len2] == s.length();
      17.   }
      18. }