Description:
Given 3 strings of all having length < 100,the task is to find the longest common sub-sequence
in all three given sequences.
Example:
Input : str1 = "geeks"
str2 = "geeksfor"
str3 = "geeksforgeeks"
Output : 5
Longest common subsequence is "geeks"
i.e., length = 5
Input : str1 = "abcd1e2"
str2 = "bc12ea"
str3 = "bd1ea"
Output : 3
Longest common subsequence is "b1e"
i.e. length = 3.
解題方法：
在兩個string中尋找LCS:
假設(shè)string1的長度為m，string2的長度為n。
則我們創(chuàng)建一個m+1 * n+1的矩陣桂躏，矩陣DP[i][j]代表的是具篇，當(dāng)取string1前i個字符和取string2前j個字符時粘室，它們的LCS長度為多少编矾。
則狀態(tài)轉(zhuǎn)移方程為：
- 當(dāng)string1[i - 1] == string2[j - 1]岖寞， 則DP[i][j] = DP[i - 1][j - 1] + 1；這代表著當(dāng)我們從string1和string2再各自取出一個字符央串，并且這兩個字符相同，這兩個
substring的LCS的長+=1碗啄。 - 否則质和，
DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
這道題是尋找兩個string的LCS的升級版。
狀態(tài)轉(zhuǎn)移方程為：
- 當(dāng)string1[x - 1] == string2[y - 1] == string3[z - 1]稚字， 則DP[x][y][z] = DP[x - 1][y - 1][z - 1] + 1饲宿；
- 否則，
DP[x][y][z] = max(DP[x - 1][y][z], DP[x][y - 1][z], DP[x][y][z - 1]);
Time Complexity：
O(n^3)
完整代碼：
int longestSubSequence(string& str1, string& str2, string& str3) {
int size1 = str1.size(), size2 = str2.size(), size3 = str3.size();
vector<vector<vector<int>>> DP(size1 + 1, vector<vector<int>>(size2 + 1, vector<int>(size3 + 1, 0)));
for(int x = 1; x <= size1; x++) {
for(int y = 1; y <= size2; y++) {
for(int z = 1; z <= size3; z++) {
if(str1[x - 1] == str2[y - 1] && str2[y - 1] == str3[z - 1]) {
cout<<str1[x]<<endl;
DP[x][y][z] = DP[x - 1][y - 1][z - 1] + 1;
}
else
DP[x][y][z] = max(DP[x - 1][y][z], max(DP[x][y -1][z], DP[x][y][z - 1]));
}
}
}
return DP[size1][size2][size3];
}
