Memoization ( 1D , 2D and 3D ) | A recursive implementation of LCS problem of three strings ; Utility function to get max of 2 integers ; Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; base case ; if equal , then check for next combination ; recursive call ; return the maximum of the three other possible states in recursion ; Driver code
class GFG { static int max ( int a , int b ) { return ( a > b ) ? a : b ; } static int lcs ( char [ ] X , char [ ] Y , char [ ] Z , int m , int n , int o ) { if ( m == 0 n == 0 o == 0 ) return 0 ; if ( X [ m - 1 ] == Y [ n - 1 ] && Y [ n - 1 ] == Z [ o - 1 ] ) { return 1 + lcs ( X , Y , Z , m - 1 , n - 1 , o - 1 ) ; } else { return Math . max ( lcs ( X , Y , Z , m , n - 1 , o ) , Math . max ( lcs ( X , Y , Z , m - 1 , n , o ) , lcs ( X , Y , Z , m , n , o - 1 ) ) ) ; } } public static void main ( String [ ] args ) { char [ ] X = " geeks " . toCharArray ( ) ; char [ ] Y = " geeksfor " . toCharArray ( ) ; char [ ] Z = " geeksforge " . toCharArray ( ) ; int m = X . length ; int n = Y . length ; int o = Z . length ; System . out . println ( " Length ▁ of ▁ LCS ▁ is ▁ " + lcs ( X , Y , Z , m , n , o ) ) ; } }