LCS of three strings
Given 3 strings of all having length < 100,the task is to find the longest common sub-sequence in all three given sequences.
Examples:
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.
class Solution {
public int lcsOf3(String X, String Y, String Z) {
int m = X.length(), n = Y.length(), o = Z.length();
int[][][] L = new int[m + 1][n + 1][o + 1];
/*
* Following steps build L[m+1][n+1][o+1] in bottom up fashion. Note that
* L[i][j][k] contains length of LCS of X[0..i-1] and Y[0..j-1] and Z[0.....k-1]
*/
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= o; k++) {
// Base case -> if length of any string is 0 then max subsequence=0
if (i == 0 || j == 0 || k == 0)
L[i][j][k] = 0;
else if (X.charAt(i - 1) == Y.charAt(j - 1) && X.charAt(i - 1) == Z.charAt(k - 1))
L[i][j][k] = L[i - 1][j - 1][k - 1] + 1;
else
L[i][j][k] = Math.max(Math.max(L[i - 1][j][k], L[i][j - 1][k]), L[i][j][k - 1]);
}
}
}
return L[m][n][o];
}
}
Last updated