1143.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.

翻譯

有兩個字串 text1, text2，求最長共同子序列的長度。

子序列的意思是一個字串 B 是根據另一個字串 A 產生的，不改變順序的情況下，取 A 中的某些字元組成新的字串 B。

舉例來說， "ace" 就是 "abcde" 的其中一個子序列，共同子序列就是兩個字串同時都擁有的子序列。

Example:

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

Example2:

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

思路

一、極限值/特殊狀況

• 若沒有共同子序列則回傳 0

二、哪種資料結構解

dynamic programmer 動態規劃

三、大概會怎麼解

• 若不懂動態規劃請先去了解，可參考這兩篇文章:

  • dynamic-programming - programiz

  • longest-common-subsequence - programiz

• 根據動態規劃的規則，逐字比較。

• 用二維陣列儲存比較後的結果。

型別

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */

解題

var longestCommonSubsequence = function (str1, str2) {
  let m = str1.length;
  let n = str2.length;
  // 建立一個 n+1 * m+1 的二維陣列
  const table = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  // 判斷是否欄與列相等，並存下結果
  for (i = 1; i <= m; i++) {
    for (j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1])
        table[i][j] = table[i - 1][j - 1] + 1;
      else table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
    }
  }

  return table[m][n];
};