human
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"
Solution in Python:
assistant
#Here is code to a Space Optimized Solution of LCS and the other steps required.
 def lcs ( X , Y ) :
	m = len ( X )
	n = len ( Y )
	L = [ [ 0 for i in range ( n + 1 ) ] for j in range ( 2 ) ]
	bi = bool
	for i in range ( m ) :
		bi = i & 1
		for j in range ( n + 1 ) :
			if ( i == 0 or j == 0 ) :
				L [ bi ] [ j ] = 0
			elif ( X [ i ] == Y [ j - 1 ] ) :
				L [ bi ] [ j ] = L [ 1 - bi ] [ j - 1 ] + 1
			else :
				L [ bi ] [ j ] = max ( L [ 1 - bi ] [ j ] , L [ bi ] [ j - 1 ] )
	return L [ bi ] [ n ]
X = " AGGTAB "
Y = " GXTXAYB "
print ( " Length ▁ of ▁ LCS ▁ is " , lcs ( X , Y ) )