1143.最长公共子序列

1143.最长公共子序列

1143. 最长公共子序列

一、题目描述

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3

解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3

解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

输入：text1 = "abc", text2 = "def"
输出：0

解释：两个字符串没有公共子序列，返回 0。

二、方法一：暴力法

​ 一开始打算用最笨的方法，遍历列举所有情况，思路是这样的：

• 先筛选出哪个是长串t1，哪个是短串t2，记i，j分别是t1，t2遍历的下标。
• 如果t1[i] == t2[j]，则i，j同时移动，判断接下来是否存在相同字符
• 如果t1[i] != t2[j]，则i移动，j不动。
• 如果i到达了串尾，j还没到，则i=0重新再来遍历一遍

​ 我发现我没有逻辑依据，就凭空的移动i，j两个指针，最后无法满足大部分情况，在第7个例子：“ezupkr” “ubmrapg” 跪下了。

​ 最长公共子串和字符串匹配不太相同，最长公共子串保证在串A和串B中，存在最长的公共的字符顺序。这就使得在不做备忘录的情况下，依次遍历似乎找不到这个公共序列。

//暴力法
public int longestCommonSubsequence(String text1, String text2) {

  if(text1.length() == 0 || text2.length() == 0){
    return 0;
  }

  //得到最长最短串
  String t1 = text1.length() >= text2.length() ? text1 : text2;
  String t2 = text1.length() < text2.length() ? text1 : text2;

  int result = 0;

  int length = t1.length();  //最长的串长度
  int length1 = t2.length();   //最短的串长度


  int i = 0;  //最长串每趟遍历的下标
  int j = 0;  //最短串每趟遍历的下标

  //只有当最短串遍历完才算结束  eg: "psnw","vozsh", eg:"ezupkr" "ubmrapg", eg:"acace","abcde" 
  //短串遍历完时，长串也必须遍历完 eg: "abcde","ace"
  //"ezupkr","ubmrapg"
  while(j < (length1 - 1) || i < length){

    // System.out.println(i + "...." + j);

    //如果i已经遍历到头，先判断j是否到头
    //如果j未到头，则i从0开始，短串j移动，启动新一轮的遍历
    //如果j到头，,则比较i与j字符是否相等，再结束遍历
    if(i == (length - 1)){
      if(j < (length1 - 1)){
        i = 0;
        j++; 
      }else{
        if(t1.charAt(i) == t2.charAt(j)){
          result += 1;
        }
        i++;
        j++;
      }
    }else{
      //如果i与j字符相同，则result + 1, 长短串同时向后遍历一个单位
      if(t1.charAt(i) == t2.charAt(j)){
        i++;
        j++;
        result += 1;
      }
      //如果i与j字符不同，则长串向后遍历一个单位，短串不动
      else{
        i++;
      }
    }
  }

  return result;
}

三、方法二、动态规划

​ 我理解的动态规划是指大问题的解依赖于子问题的解，第i个状态依赖于第i-1个状态，然而这道题是两个字符串，所以第[i，j]状态依赖于第[i-1，j]和[i, j - 1]的状态，主要是这个状态转移方程怎么找的问题

分析1：

• 如果t1[ i ] != t2[j] ，则dp[ i ][ j ] = max（dp[ i - 1 ][ j ]，dp[ i ][ j - 1 ]）；
• 如果t1[ i ] == t2[j] ，则dp[ i ][ j ] = max（dp[ i - 1 ][ j ]，dp[ i ][ j - 1 ]） + 1；

这时会发现这种方法在在**“abcde”，“ace"没问题，但在"bsbininm”，“jmjkbkjkv”**上出现问题

输入："bsbininm"，"jmjkbkjkv"
错误输出：2
正确输出：1

---

分析2：

​ 如果text1[i] != text2[j]，dp[ i ][ j ]依赖于上一个状态dp[i-1][j-1]。上一个状态是没加入要比较的字符text1[i]，text2[j]的text1，text2子串，斜上方是上一个状态，不是max(左方，上方)

• 如果t1[ i ] != t2[j] ，则dp[ i ][ j ] = dp[ i - 1 ][ j - 1]；
• 如果t1[ i ] == t2[j] ，则dp[ i ][ j ] = dp[ i - 1 ][ j - 1] + 1；

这时会发现这种方法在**“bsbininm”，“jmjkbkjkv"没问题，在"abcde”，“ace”**上出现问题

输入："abcde"，"ace"
错误输出：1
正确输出：3

---

分析3：

• 如果t1[ i ] != t2[j] ，则dp[ i ][ j ] = max（dp[ i - 1 ][ j ]，dp[ i ][ j - 1 ]）；
• 如果t1[ i ] == t2[j] ，则dp[ i ][ j ] = min（dp[ i - 1 ][ j ]，dp[ i ][ j - 1 ]） + 1；

这时会发现这种方法在**“bsbininm”，“jmjkbkjkv”** 或者 “abcde”，“ace"上没问题，但在"bmvcnwrmxcfcxabkxcvgbozmpspsbenazglyxkpibgzq”，**“bmpmlstotylonkvmhqjyxmnqzctonqtobahcrcbibgzgx”**上出现问题

输入："bmvcnwrmxcfcxabkxcvgbozmpspsbenazglyxkpibgzq"
	 "bmpmlstotylonkvmhqjyxmnqzctonqtobahcrcbibgzgx"
错误输出：14
正确输出：13

---

分析4：

​ 考虑三个方向，及dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]

• 如果t1[ i ] != t2[j] ，则dp[ i ][ j ] = max（dp[ i - 1 ][ j ]，dp[ i ][ j - 1 ]，dp[i-1][j-1]）；
• 如果t1[ i ] == t2[j] ，则dp[ i ][ j ] = min（dp[ i - 1 ][ j ]，dp[ i ][ j - 1 ]，dp[i-1][j-1]） + 1；

参考题解 https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/

---

代码如下：

class Solution {

  public int longestCommonSubsequence(String text1, String text2) {

    if(text1.length() == 0 || text2.length() == 0) return 0;

    //维护一个二维数组，由于第i行，j列依赖与i-1，j-1的状态，所以预留出多余的第一列，第一行，且为0
    int dp[][] = new int[text1.length() + 1][text2.length() + 1];

    // //第1列全为0
    // for(int i = 0; i < dp.length; i++){
    //     dp[i][0] = 0;
    // }

    //  //第1行全为0
    //  for(int i = 0; i < dp[0].length; i++){
    //     dp[0][i] = 0;
    // }

    int max = 0;
    int max_i = 0, max_j = 0;
    for(int i = 1; i < dp.length; i++){
      for(int j = 1; j < dp[0].length; j++){

        //如果text1[i] != text2[j],则dp[i][j]依赖于上一个状态，及dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三者选最大
        if(text1.charAt(i - 1) != text2.charAt(j - 1)){
          dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
          dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1]);
        }
        //如果text1[i] == text2[j],则dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
        else{
          int min = Math.min(dp[i-1][j],dp[i][j-1]);
          min = Math.min(min, dp[i-1][j-1]);
          dp[i][j] = min + 1;
        }

        if(max < dp[i][j]){
          max = dp[i][j];
          max_i = i;
          max_j = j;
        }
      }
    }

    return max;
  }

Accepted

• 38/38 cases passed (18 ms)
• Your runtime beats 21.36 % of java submissions
• Your memory usage beats 8.33 % of java submissions (43.5 MB)

四、补充：打印输出最长公共子串

​ 从最大值开始，记录坐标，采用逆推法输出最长公共子串

• 如果text1[i] != text2[j]，找到三个方向的最大值，如果相等，默认斜向上
• 如果text1[i] == text2[j]，先拼接sub，找到三个方向的最小值，默认斜向上

if(max != 0){

  String sub = "";  

  /**
             * 逆推法：
             * 如果text1[i] != text2[j]，找到三个方向的最大值
             * 如果text1[i] == text2[j]，先拼接sub，找到三个方向的最小值，默认斜向上
             */
  int i = max_i, j = max_j;

  //判断最大值max是从哪里变过来的,注意边界处理
  while(i >= 1 && j >= 1){

    int a1 = dp[i-1][j]; //上方
    int a2 = dp[i][j-1]; //左方
    int a3 = dp[i-1][j-1]; //斜上方

    if(text1.charAt(i - 1) == text2.charAt(j - 1)){

      sub += text1.charAt(i - 1);

      //选最小值
      if(a1 < a2){
        if(a1 < a3){
          i = i-1;
        }else{
          i = i-1;
          j = j-1;
        }
      }else{
        if(a2 < a3){
          j = j-1;
        }
        //如果三个数相等，走斜上方
        else{
          i = i-1;
          j = j-1;
        }
      }

    }else{
      //选最大值
      if(a1 > a2){
        if(a1 > a3){
          i = i-1;
        }else{
          i = i-1;
          j = j-1;
        }
      }else{
        if(a2 > a3){
          j = j-1;
        }
        //如果三个数相等，走斜上方
        else{
          i = i-1;
          j = j-1;
        }
      }
    }
  }

  //反向打印sub
  for(int k = sub.length() -1; k >= 0; k--){
    System.out.print(sub.charAt(k));
  }
}

以第36个例子为例

"bmvcnwrmxcfcxabkxcvgbozmpspsbenazglyxkpibgzq"
"bmpmlstotylonkvmhqjyxmnqzctonqtobahcrcbibgzgx"

Output (8 ms)
13

Expected Answer
13

Stdout
bmnmxcbcbbzgx

五：心得体会

• 之前了解到动态规划的题一开始用暴力法来解，做题顺序如下：暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法https://github.com/labuladong/fucking-algorithm/tree/master/动态规划系列。但是我硬是想不出来暴力解法。该题两个字符串同时作为变量，用一维的暴力法遍历好像不能够解决（如果有小伙伴可以解决的话，请告诉我一下，我想和你探讨一下）。
• 用二维数组的动态规划算法在控制两个变量上很清晰，斜上方，左方，上方均为上一次的状态。动态规划就好像二维的平面直角坐标系。
• 好好体会将问题分解成子问题，并对子问题的解进行剪枝，抛弃一些无用的解，存放到二维的dp数组中，要明确本题中二维数组的定义是什么。