A Space Optimized Solution of LCS | Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Find lengths of two strings ; Binary index , used to index current row and previous row . ; Compute current binary index ; Last filled entry contains length of LCS for X [ 0. . n - 1 ] and Y [ 0. . m - 1 ] ; Driver Code
def lcs ( X , Y ) : NEW_LINE INDENT m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE L = [ [ 0 for i in range ( n + 1 ) ] for j in range ( 2 ) ] NEW_LINE bi = bool NEW_LINE for i in range ( m ) : NEW_LINE INDENT bi = i & 1 NEW_LINE for j in range ( n + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT L [ bi ] [ j ] = 0 NEW_LINE DEDENT elif ( X [ i ] == Y [ j - 1 ] ) : NEW_LINE INDENT L [ bi ] [ j ] = L [ 1 - bi ] [ j - 1 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT L [ bi ] [ j ] = max ( L [ 1 - bi ] [ j ] , L [ bi ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return L [ bi ] [ n ] NEW_LINE DEDENT X = " AGGTAB " NEW_LINE Y = " GXTXAYB " NEW_LINE print ( " Length ▁ of ▁ LCS ▁ is " , lcs ( X , Y ) ) NEW_LINE