题目描述
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.
Example1:
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.
Example3:
Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.
Constraints:
- 1 <= text1.length <= 1000
- 1 <= text2.length <= 1000
- The input strings consist of lowercase English characters only.
解题思路
- dp思想
- 当我们扫描到text1的第iii个字符，text2的第jjj个字符时，需要考虑这两个字符是否相等，如果这两个字符相等，很明显，计算出的结果应该是text1的前i−1i - 1i−1和text2的前j−1j - 1j−1个计算出的最长子字符串的长度加1，即：
dp[i][j]=dp[i−1][j−1]+1
- 当两个字符不相等时，我们就需要考虑dp[i−1][j]以及dp[i][j−1]，因为当前的两个字符已经不相等了，所以我们没有办法在原有的基础上更进一步，只能在dp[i−1][j]以及dp[i][j−1]中选择一个最大值，即：
dp[i][j]=max(dp[i−1][j],dp[i][j−1])
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int row = text1.size();
int col = text2.size();
vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
for(int i = 1; i <= row; i++){
for(int j = 1; j <= col; 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[row][col];
}
};
