java_longest_common_subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

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.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Examples

Example 1:

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

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

解析

給定兩個字串 text1, text2

要求寫一個演算法找出 text1, text2 最大共同子字串的長度

這邊定義每個字串 s 的子字串 是從 s 的字元中刪除幾個字元所形成的字串

共同子字串 common_substring 代表 同時是 text1, text2 的子字串

len(common_substring) ≤ min(len(text1), len(text2))

要透過動態規劃的作法

先思考如何去找出該問題的子問題

舉例來說： text1: “abcde”, text2: “ace”

當發現 兩個字串的第一個字元相等

找 “abcde” , “ace” 最長子字串長度 = 1 + “bcde”, “ce” 最長子字串長度

如果是順向去找會發現有些字串會重複查找

可以從反向來思考

兩個字串都以從第i 個位置到最後逐步考慮更長字串所能找到的子字串

首先定義 d[i][j]

第1個字串從第i個位置開始從第 i 字元開始與

第2個字串 從第 j 個開始所形成的最長字串長度

可以發現

d[i][j] = d[i+1][j+1]+1 , if text1[i] == text2[j]

d[i][j] = max(d[i+1][j], d[i][j+1]) if text1[i] ≠ text2[j]

程式碼

public class Solution {
  public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m+1][n+1];
    // from last index to calculate max common substring length
    // dp[i][j] = dp[i+1][j+1]+1 if text1[i] == text2[j]
    // dp[i][j] = max(dp[i+1][j], dp[i][j+1]) if text1[i] != text2[j]
    for (int i = m-1; i >= 0; i--) {
      for (int j = n-1; j >= 0; j--) {
        if (text1.charAt(i) == text2.charAt(j)) {
          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[0][0];
  }
}

困難點

1. 要能找出最長子字串的遞迴子關係

Solve Point

• 建立一個 m+1 by n+1 的整數矩陣 dp 用來儲存動態規劃的中間計算結果
• 透過 dp[i][j] 的遞迴關係式從 i = m+1, j = n+1 逐步往前推算
• 回傳 dp[0][0]