Shortest Common Supersequence | Returns length of the shortest supersequence of X and Y ; Fill table in bottom up manner ; Below steps follow above recurrence ; Driver Code
def superSeq ( X , Y , m , n ) : NEW_LINE INDENT dp = [ [ 0 ] * ( n + 2 ) for i in range ( m + 2 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if ( not i ) : NEW_LINE INDENT dp [ i ] [ j ] = j NEW_LINE DEDENT elif ( not j ) : NEW_LINE INDENT dp [ i ] [ j ] = i NEW_LINE DEDENT elif ( X [ i - 1 ] == Y [ j - 1 ] ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = 1 + min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ m ] [ n ] NEW_LINE DEDENT X = " AGGTAB " NEW_LINE Y = " GXTXAYB " NEW_LINE print ( " Length ▁ of ▁ the ▁ shortest ▁ supersequence ▁ is ▁ % d " % superSeq ( X , Y , len ( X ) , len ( Y ) ) ) NEW_LINE