Shortest Uncommon Subsequence | A simple recursive Python program to find shortest uncommon subsequence . ; A recursive function to find the length of shortest uncommon subsequence ; S String is empty ; T String is empty ; Loop to search for current character ; char not found in T ; Return minimum of following two Not including current char in answer Including current char ; Driver code
MAX = 1005 NEW_LINE def shortestSeq ( S , T , m , n ) : NEW_LINE INDENT if m == 0 : NEW_LINE INDENT return MAX NEW_LINE DEDENT if ( n <= 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT for k in range ( n ) : NEW_LINE INDENT if ( T [ k ] == S [ 0 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( k == n ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT return min ( shortestSeq ( S [ 1 : ] , T , m - 1 , n ) , 1 + shortestSeq ( ( S [ 1 : ] ) , T [ k + 1 : ] , m - 1 , n - k - 1 ) ) NEW_LINE DEDENT S = " babab " NEW_LINE T = " babba " NEW_LINE m = len ( S ) NEW_LINE n = len ( T ) NEW_LINE ans = shortestSeq ( S , T , m , n ) NEW_LINE if ( ans >= MAX ) : NEW_LINE INDENT ans = - 1 NEW_LINE DEDENT print ( " Length ▁ of ▁ shortest ▁ subsequence ▁ is : " , ans ) NEW_LINE