題意
給定兩個字元串
text1
和
text2
,傳回這兩個字元串的最長公共子序列的長度。
一個字元串的 子序列 是指這樣一個新的字元串:它是由原字元串在不改變字元的相對順序的情況下删除某些字元(也可以不删除任何字元)後組成的新字元串。
例如,
"ace"
是
"abcde"
的子序列,但
"aec"
不是
"abcde"
的子序列。兩個字元串的「公共子序列」是這兩個字元串所共同擁有的子序列。
若這兩個字元串沒有公共子序列,則傳回 0。
題解
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.size();
int len2 = text2.size();
int dp[len1+1][len2+1];
for(int i = 0; i <= len1; i++)
for(int j = 0; j <= len2; j++)
dp[i][j] = 0;
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; 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[len1][len2];
}
};