[toc]

题目描述

给定两个字符串text1 和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：

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

思路

采用动态规划的思想来做
m为text1的长度
n为text2的长度
新建一个dp[m][n]二维数组来保存每个状态下的最大公共子序列,比如dp[i][j]表示text1的0-i的子字符串和text2的0-j的子字符串的最大公共子序列
然后循环对两个字符串的每个字母进行判断,有以下两种情况:

  • 情况一:
    text1[i]=text2[j],这个时候dp[i][j]就等于text1[0:i-1]和text2[0:j-1]的最大公共子序列长度+1,即dp[i][j]=dp[i-1][j-1]+1
  • 情况二:
    text1[i]!=text2[j],这时候dp[i][j]就取前面text1[0:i-1]和text2[0:j]与text1[0:i]和text2[0:j-1]之间的最大值,即dp[i][j] = max(dp[i-1][j],dp[i][j-1])

最后再对默认情况加上限定:

  • 情况一中,当i和j中有一个为0的那就表示他们没有dp[i-1][j-1]值,那么就直接赋值为1
  • 情况二中
    • 当i=0,j>0: dp[i][j] = dp[i][j-1];
    • 当j=0,i>0 dp[i][j] = dp[i-1][j];
    • 当i=0,j=0 dp[i][j] = 0;

最终返回dp[m-1][n-1]即为两个字符串的最长公共子序列的长度

代码实现

  1. class Solution {
  2.     public int longestCommonSubsequence(String text1, String text2) {
  3.         // 新建一个二维的dp数组,dp[i][j]表示text1的0-i的子字符串和text2的0-j的子字符串的最大公共子序列
  4.         int len1 = text1.length();
  5.         int len2 = text2.length();
  6.         int[][] dp = new int[len1][len2];
  7.         // 循环比较
  8.         for(int i=0;i<len1;i++){
  9.             for(int j=0;j<len2;j++){
  10.                 // 情况1: 当text1[0:i]=text2[0:j]那么dp[i][j]=dp[i-1][j-1]+1
  11.                 if(text1.charAt(i) == text2.charAt(j)){
  12.                     if(i==0 || j==0){
  13.                         dp[i][j] = 1;
  14.                     }else{
  15.                         dp[i][j] = dp[i-1][j-1]+1;
  16.                     }
  17.                 }else{
  18.                 // 情况2: 当text1[0:i]!=text2[0:j] dp[i][j] = max(dp[i-1][j],dp[i][j-1])
  19.                     if(i==0 && j>0){
  20.                         dp[i][j] = dp[i][j-1];
  21.                     }else if(j==0 && i>0){
  22.                         dp[i][j] = dp[i-1][j];
  23.                     }else if(i==0 && j==0){
  24.                         dp[i][j] = 0;
  25.                     }else{
  26.                         dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
  27.                     }
  28.                 }
  29.             }
  30.         }
  31.         return dp[len1-1][len2-1];
  32.     }
  33. }