LeetCode 1143. Longest Common Subsequence

Description:

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.

Solution:

使用动态规划，对于每个可能的dp[i][j]组合，其转移方程如下：

dp[i][j] = dp[i - 1][j - 1] + 1; //当a.charAt(i) == b.charAt(j)dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); //当a.charAt(i) == b.charAt(j)

dp[i][j] 表示字符串a中第i个字符作为结尾和字符串b中第j个字符作为结尾的字符串最长公共子序列。当a.charAt(i) == b.charAt(j)；最长子序列会增长一位。

java 代码如下：

public int longestCommonSubsequence(String a, String b) {int[][] dp = new int[a.length() + 1][b.length() + 1];for(int i = 1; i <= a.length(); ++i) {for(int j = 1; j <= b.length(); ++j) {if(a.charAt(i - 1) == b.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[a.length()][b.length()];}

把生成的dp矩阵打印如下：

0 0 0 0 0 0 00 0 0 0 1 1 10 1 1 1 1 2 20 1 1 2 2 2 20 1 1 2 2 3 30 1 2 2 2 3 30 1 2 2 3 3 40 1 2 2 3 4 4