# 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:

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

Example2:

```js
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](https://www.programiz.com/dsa/dynamic-programming)
  * [longest-common-subsequence - programiz](https://www.programiz.com/dsa/longest-common-subsequence)
* 根據動態規劃的規則，逐字比較。
* 用二維陣列儲存比較後的結果。

## **型別**

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

## **解題**

```js
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];
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://rock070.gitbook.io/leetcode-with-js/dynamic-programming-dong-tai-gui-hua/index.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.