LCS ( Longest Common Subsequence ) of three strings | Python3 program to find LCS of three strings ; Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] and Z [ 0. . o - 1 ] ; Driver code
X = " AGGT12" NEW_LINE Y = "12TXAYB " NEW_LINE Z = "12XBA " NEW_LINE dp = [ [ [ - 1 for i in range ( 100 ) ] for j in range ( 100 ) ] for k in range ( 100 ) ] NEW_LINE def lcsOf3 ( i , j , k ) : NEW_LINE INDENT if ( i == - 1 or j == - 1 or k == - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ j ] [ k ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] [ k ] NEW_LINE DEDENT if ( X [ i ] == Y [ j ] and Y [ j ] == Z [ k ] ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = 1 + lcsOf3 ( i - 1 , j - 1 , k - 1 ) NEW_LINE return dp [ i ] [ j ] [ k ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = max ( max ( lcsOf3 ( i - 1 , j , k ) , lcsOf3 ( i , j - 1 , k ) ) , lcsOf3 ( i , j , k - 1 ) ) NEW_LINE return dp [ i ] [ j ] [ k ] NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE o = len ( Z ) NEW_LINE print ( " Length ▁ of ▁ LCS ▁ is " , lcsOf3 ( m - 1 , n - 1 , o - 1 ) ) NEW_LINE DEDENT