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