1143.最长公共子序列。3星

方法一：

   public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(), n2 = text2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; 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[n1][n2];
    }

对于两个子序列 S1 和 S2，找出它们最长的公共子序列。

定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为两种情况：

1.当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。
2. 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。

作者：bryank-3
链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/jian-dan-yi-dong-zui-chang-gong-gong-zi-xu-lie-by-/
来源：力扣（LeetCode）

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

n1=3;
n2=5;
dp=int[4][6];
判断条件：text1.charAt(i - 1) == text2.charAt(j - 1)

n2\n1	1:a	2:b	3:c	4:d	5:e
1:a	‘a’==‘a’；dp[i][j] = dp[i - 1][j - 1] + 1； =1	‘a’ !=‘b’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1	‘a’ !=‘c’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1	‘a’ !=‘d’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1	‘a’ !=‘e’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1
2:c	‘c’ !=‘a’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1	‘c’ !=‘b’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1	‘c’==‘c’；dp[i][j] = dp[i - 1][j - 1] + 1；=2	‘c’ !=‘d’；Math.max(dp[i - 1][j], dp[i][j - 1])；=2	‘c’ !=‘e’；Math.max(dp[i - 1][j], dp[i][j - 1])；=2
3:e	‘e’ !=‘a’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1	‘e’ !=‘b’；Math.max(dp[i - 1][j], dp[i][j - 1])；=1	‘e’ !=‘c’；Math.max(dp[i - 1][j], dp[i][j - 1])；=2	‘e’ !=‘d’；Math.max(dp[i - 1][j], dp[i][j - 1])；=2	‘e’==‘e’；dp[i][j] = dp[i - 1][j - 1] + 1；=3

方法二：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
   
	if (text1 == null || text2 == null) return 0;
	//存在有一方字符串为空，则返回0（该判空和下面长度判空可去其一）
	int len1 = text1.length(), len2 = text2.length();
	if (len1 == 0 || len2 == 0) return 0;
	//有一方字符串长度为0，则返回0
	char[] colText, rowText;
	if (len1 > len2) {
		colText = text2.toCharArray();
		rowText = text1.toCharArray();
	} else {
		colText = text1.toCharArray();
		rowText = text2.toCharArray();
	}
	//将text1和text2转为字符串数组，长的为行数组，另一个为列数组
	int[] dp = new int[colText.length + 1];//最终统计出来的，dp[j]为列数组的前j位和行数组的最大公共子序列
	//int数组，长度为列字符串数组长度加一；用来：
	for (int i = 1; i <= rowText.length; i++) {
	//双层循环遍历两个字符串
		int tmp = 0;
		//定义一个整型变量tmp初值为0；用来：
		for (int j = 1; j <= colText.length; j++) {
			int prev = tmp;
			//定义一个整型变量prev,赋值为tmp
			tmp = dp[j];
			//tmp赋值为dp[i]
			if (rowText[i - 1] == colText[j - 1]) {
				dp[j] = prev + 1;
			} else {
				dp[j] = Math.max(dp[j], dp[j - 1]);
			}
		}
	}
	return dp[colText.length];
}
    
}

作者：codermjlee
链接：https://leetcode-cn.com/problems/longest-common-subsequence/solution/hao-shi-kong-jian-da-bai-100yong-de-yi-wei-shu-zu-/
来源：力扣（LeetCode）
。

//-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结合方法二，对方法一改进，使用字符串数组变量，可节省一定时间提高效率：

 class Solution {
  public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(), n2 = text2.length();
        if (n1 == 0 || n2 == 0) return 0;
        int[][] dp = new int[n1 + 1][n2 + 1];
        char[] tx1=text1.toCharArray();
        char[] tx2=text2.toCharArray();
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (tx1[i - 1] == tx2[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[n1][n2];
    }
  }