dp第19天

392. 判断子序列

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

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

 进阶：

 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

 致谢：

 特别感谢 @pbrother 添加此问题并且创建所有测试用例。



 示例 1：

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

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


 提示：

 0 <= s.length <= 100
 0 <= t.length <= 10^4
 两个字符串都只由小写字符组成。


 * @author zeroheart
 *
 */
public class Question392 {

   public boolean isSubsequence(String s, String t) {
      // 这题也不用dp了吧。。
      int sl = s.length();
      int tl = t.length();

      int i = 0;
      int j = 0;
      while (i<sl && j<tl){
         if(s.charAt(i) == t.charAt(j)){
            i++;
            j++;
         }else {
            j++;
         }
      }

      return i == sl;

   }

   public static void main(String args[]){
   }
}

1143. 最长公共子序列

这也是经典题目

dp[i][j] 表示的是0-i和0-j的最长公共字串

递推公式：

if(text1.charAt(i-1) == text2.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]);
            }

/**
 *
 1143. 最长公共子序列
 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。



 示例 1：

 输入：text1 = "abcde", text2 = "ace"
 输出：3
 解释：最长公共子序列是 "ace" ，它的长度为 3 。
 示例 2：

 输入：text1 = "abc", text2 = "abc"
 输出：3
 解释：最长公共子序列是 "abc" ，它的长度为 3 。
 示例 3：

 输入：text1 = "abc", text2 = "def"
 输出：0
 解释：两个字符串没有公共子序列，返回 0 。


 提示：

 1 <= text1.length, text2.length <= 1000
 text1 和 text2 仅由小写英文字符组成。

 * @author zeroheart
 *
 */
public class Question1143 {

   public int longestCommonSubsequence(String text1, String text2) {
      // dp[i][j] 表示的是0-i和0-j的最长公共字串
      int len1 = text1.length();
      int len2 = text2.length();

      int[][] dp = new int[len1+1][len2+1];

      for(int i = 1; i<len1; i++){
         for(int j = 1; j<len2; j++){
            if(text1.charAt(i-1) == text2.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]);
            }
         }
      }

      return dp[len1][len2];
   }

   public static void main(String args[]){
   }
}