給定兩個字串，傳回它們最長公共子序列（longest common subsequence, LCS）的長度。
題目連結：連結點此。
題目描述
給定兩個字串 text1 和 text2，傳回它們最長公共子序列（longest common subsequence, LCS）的長度。如果沒有公共子序列，則傳回 0。
字串的子序列（subsequence）是指在不改變剩餘字元相對順序的情況下，從原始字串中刪除部分字元（可以不刪除）產生的新字串。
例如，“ace”是“abcde”的子序列。
兩個字串的公共子序列（common subsequence）是指兩個字串共同的子序列。
題目限制
1 <= text1.length, text2.length <= 1000text1andtext2consist of only lowercase English characters.
解題方法
1. 首先我們可以把text1的每個字元當成橫列，把text2的每個字元當成縱列，並且宣告一個二維向量儲存兩個輸入字串的每個字元的LCS長度，dp[i][j]表示text1前i個字符（text1[0:i]）與text2前j個字符（text2[0:j]）的LCS長度。
int m = text1.length();
int n = text2.length();
vector<vector<int>> dp(m, vector<int>(n, 0));我們使用text1=”abcde”、text2=”ace”作為範例，宣告的二維向量dp會是下列表格的樣子。第一個直行和第一個橫列為空字元，但dp宣告時不包含空字元的行列，計算時會直接把他當為數值0。
| ” | a | b | c | d | e | |
| ” | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | dp[0][0] | dp[1][0] | … | ||
| c | 0 | dp[0][1] | ||||
| e | 0 | … |
2. 用雙層for迴圈遍歷text1和text2的每個字元。
for (int i = 0; i < m; i++) //遍歷text1的每個字元
{
for (int j = 0; j < n; j++) //遍歷text2的每個字元
{
}
}3. 若該格子對應的兩個字母相同，答案 = 1 + 左斜上格。
dp[i-1][j-1] 表示 text1 前 i-1 個字符（text1[0:i-1]）與 text2 前 j-1 個字符（text2[0:j-1]）的 LCS 長度，也就是不包含當前字符 text1[i-1] 和 text2[j-1] 的子問題答案，如果 text1[i] == text2[j]，則當前字符可以加入 LCS，總長度增加 1，因此 dp[i][j] = dp[i-1][j-1] + 1。
if (text1[i] == text2[j])
{
if (i > 0 && j > 0) dp[i][j] = 1 + dp[i - 1][j - 1];
else dp[i][j] = 1 + 0;
}4. 若該格子對應的兩個字母不相同，答案 = Max(左邊格, 上面格)。
如果text1[i] != text2[j]，表示text1的當前字元和text2的當前字元都無法加入LCS，此時我們需要從以下兩個子問題作選擇：
- 忽略 text1的當前字符：計算 text1 的前 i-1 個字符與 text2 的前 j 個字符的 LCS，即 dp[i-1][j]（上面格）。
- 忽略 text2 的當前字符：計算 text1 的前 i 個字符與 text2 的前 j-1 個字符的 LCS，即 dp[i][j-1]（左邊格）。
因此我們選擇兩種子問題中 LCS 長度較大的那一個。
else
{
if (i > 0 && j > 0) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
else if (i > 0) dp[i][j] = dp[i - 1][j];
else if (j > 0) dp[i][j] = dp[i][j - 1];
else dp[i][j] = 0;
}遍歷完成後，二維向量dp會是下列表格的樣子。
| ” | a | b | c | d | e | |
| ” | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 | 1 | 1 |
| c | 0 | 1 | 1 | 2 | 2 | 2 |
| e | 0 | 1 | 1 | 2 | 2 | 3 |
5. 返回最後一個格子的數值：dp[m – 1][n – 1]，意思為text1的字元[0:m-1]與text2的字元[0:n-1]的LCS長度，即題目要求。
return dp[m - 1][n - 1];完整程式碼
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
//1.變數宣告
//把text1的每個字元當成橫列，把text2的每個字元當成縱列
int m = text1.length();
int n = text2.length();
vector<vector<int>> dp(m, vector<int>(n, 0));
//2.用雙層for迴圈遍歷text1和text2的每個字元
for (int i = 0; i < m; i++) //遍歷text1的每個字元
{
for (int j = 0; j < n; j++) //遍歷text2的每個字元
{
//3.若該格子對應的兩個字母相同，答案 = 1 + 左斜上格
if (text1[i] == text2[j])
{
if (i > 0 && j > 0) dp[i][j] = 1 + dp[i - 1][j - 1];
else dp[i][j] = 1 + 0;
}
//4.若該格子對應的兩個字母不相同，答案 = Max(左邊格, 上面格)
else
{
if (i > 0 && j > 0) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
else if (i > 0) dp[i][j] = dp[i - 1][j];
else if (j > 0) dp[i][j] = dp[i][j - 1];
else dp[i][j] = 0;
}
}
}
//5.返回最後一個格子的數值
return dp[m - 1][n - 1];
}
};測試資料
此題目最經典的測資，驗證當一個字串是另一個字串的子序列時，DP 表格的填寫是否正確。
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
測試當兩個字串完全相同時，程式是否正確返回字串的完整長度。
Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.
測試當兩個字串完全沒有共同字符時，程式是否正確返回 0。
Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.
測試最小輸入（edge case）的處理。
Input: text1 = "a", text2 = "a"
Output: 1
時間與空間複雜度
時間複雜度：O(m*n)，其中 m 和 n 分別為 text1 和 text2 的長度。因為需要遍歷 m * n 的 dp 表格。
空間複雜度：O(m*n)，因為使用了 m * n 的二維陣列儲存子問題答案。
其他相關題目
- 62. Unique Paths