human
Shortest possible combination of two strings | Prints super sequence of a [ 0. . m - 1 ] and b [ 0. . n - 1 ].
Fill table in bottom up manner.
Below steps follow above recurrence.
Following code is used to print supersequence.
Create a string of size index + 1 to store the result.
Start from the right - most - bottom - most corner and one by one store characters in res [ ].
If current character in a [ ] and b are same , then current character is part of LCS.
Put current character in result.
reduce values of i , j and indexs.
If not same , then find the larger of two and go in the direction of larger value.
Copy remaining characters of string 'a.
Copy remaining characters of string 'b.
Print the result.
Driver Code"
How can the above be solved in Python?
assistant
#Here is code to shortest possible combination of two strings and the other steps required.
 def printSuperSeq ( a , b ) :
	m = len ( a )
	n = len ( b )
	dp = [ [ 0 ] * ( n + 1 ) for i in range ( m + 1 ) ]
	for i in range ( 0 , m + 1 ) :
		for j in range ( 0 , n + 1 ) :
			if not i :
				dp [ i ] [ j ] = j ;
			elif not j :
				dp [ i ] [ j ] = i ;
			elif ( a [ i - 1 ] == b [ j - 1 ] ) :
				dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] ;
			else :
				dp [ i ] [ j ] = 1 + min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ;
	index = dp [ m ] [ n ] ;
	res = [ " " ] * ( index )
	i = m
	j = n ;
	while ( i > 0 and j > 0 ) :
		if ( a [ i - 1 ] == b [ j - 1 ] ) :
			res [ index - 1 ] = a [ i - 1 ] ;
			i -= 1
			j -= 1
			index -= 1
		elif ( dp [ i - 1 ] [ j ] < dp [ i ] [ j - 1 ] ) :
			res [ index - 1 ] = a [ i - 1 ]
			i -= 1
			index -= 1
		else :
			res [ index - 1 ] = b [ j - 1 ]
			j -= 1
			index -= 1
'
	while ( i > 0 ) :
		res [ index - 1 ] = a [ i - 1 ]
		i -= 1
		index -= 1
'
	while ( j > 0 ) :
		res [ index - 1 ] = b [ j - 1 ]
		j -= 1
		index -= 1
	print ( " " . join ( res ) )
if __name__ == ' _ _ main _ _ ' :
	a = " algorithm "
	b = " rhythm "
	printSuperSeq ( a , b )