Shortest Uncommon Subsequence | A dynamic programming based Python program to find shortest uncommon subsequence . ; Returns length of shortest common subsequence ; declaring 2D array of m + 1 rows and n + 1 columns dynamically ; T string is empty ; S string is empty ; char not present in T ; Driver Code
MAX = 1005 NEW_LINE def shortestSeq ( S : list , T : list ) : NEW_LINE INDENT m = len ( S ) NEW_LINE n = len ( T ) NEW_LINE dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( m + 1 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 1 NEW_LINE DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT dp [ 0 ] [ i ] = MAX NEW_LINE DEDENT for i in range ( 1 , m + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT ch = S [ i - 1 ] NEW_LINE k = j - 1 NEW_LINE while k >= 0 : NEW_LINE INDENT if T [ k ] == ch : NEW_LINE INDENT break NEW_LINE DEDENT k -= 1 NEW_LINE DEDENT if k == - 1 : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i - 1 ] [ j ] , dp [ i - 1 ] [ k ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT ans = dp [ m ] [ n ] NEW_LINE if ans >= MAX : NEW_LINE INDENT ans = - 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " babab " NEW_LINE T = " babba " NEW_LINE print ( " Length ▁ of ▁ shortest ▁ subsequence ▁ is : " , shortestSeq ( S , T ) ) NEW_LINE DEDENT