# 【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.

> Constraints:
> * `1 <= text1.length <= 1000`
> * `1 <= text2.length <= 1000`
> * The input strings consist of lowercase English characters only.

> 給兩個字串 `text1` 和 `text2`, 回傳它們最長共同子字串的長度。

> 一個字串的子字串是從原始字串生成的新字串，其中刪除了一些字元(可以是空字元)而不改變其餘字元的相對順序。(例如："ace"是"abcde"的子字串，而"aec"則不是)。兩個字串的共同子字串是指該子字串同時為兩者的子字串。

> 如果沒有任何共同子字串，回傳0。

> 限制：
> * `1 <= text1.length <= 1000`
> * `1 <= text2.length <= 1000`
> * 輸入字串只會包含小寫英文字母。

## Example:

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.

## Solution

* 經典的DP題目。
* 首先我們設兩個變數`m`和`n`分別為兩個字串的長度。
* 建一個DP表，且大小為`m + 1` x `n + 1`。
* 表格的意義為：`text1`和`text2`只取前`i`個和前`j`個字的時候的最長共同子字串。
* DP表大小要多一格是因為要考慮到空字串。
* 空字串一定沒有共同子字串(或者說共同子字串只有空字串)，因此表格中`i = 0`或是`j = 0`都填入`0`。
* 當`text[i] == text[j]`時，此時填入`dp[i - 1][j - 1] + 1`。
* 代表目前最長的就是去掉最後一個字的最長子字串再 +1。
* 若是不等於，填入`dp[i - 1][j]`和`dp[i][j - 1]`較大者。
* 代表不看`text1`或是`text2`的最後一個字，取較長者。
* 整理成遞迴式：
$$
dp[i][j] = \\
\left\{\begin{matrix}
0,\ i=0\ OR\ j=0
\\ dp[i-1][j-1],\ s[i]=s[j]
\\ max(dp[i-1][j], dp[i][j-1]),\ other
\end{matrix}\right.
$$
* 最後取`dp[m][n]`就是答案了。
* 前`m`個和前`n`個就是原來的兩個字串。

### Code

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length();
        int n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n ; j++)
            {
                if(text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
};

###### tags: `LeetCode` `C++`