Find shortest unique prefix for every word in a given list | Set 2 ( Using Sorting ) | Python3 program to prshortest unique prefixes for every word . ; Create an array to store the results ; Sort the array of strings ; Compare the first with its only right neighbor ; Store the unique prefix of a [ 1 ] from its left neighbor ; Compute common prefix of a [ i ] unique from its right neighbor ; Compare the new prefix with previous prefix ; Store the prefix of a [ i + 1 ] unique from its left neighbour ; Compute the unique prefix for the last in sorted array ; Driver Code
def uniquePrefix ( a ) : NEW_LINE INDENT size = len ( a ) NEW_LINE res = [ 0 ] * ( size ) NEW_LINE a = sorted ( a ) NEW_LINE j = 0 NEW_LINE while ( j < min ( len ( a [ 0 ] ) - 1 , len ( a [ 1 ] ) - 1 ) ) : NEW_LINE INDENT if ( a [ 0 ] [ j ] == a [ 1 ] [ j ] ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT ind = 0 NEW_LINE res [ ind ] = a [ 0 ] [ 0 : j + 1 ] NEW_LINE ind += 1 NEW_LINE temp_prefix = a [ 1 ] [ 0 : j + 1 ] NEW_LINE for i in range ( 1 , size - 1 ) : NEW_LINE INDENT j = 0 NEW_LINE while ( j < min ( len ( a [ i ] ) - 1 , len ( a [ i + 1 ] ) - 1 ) ) : NEW_LINE INDENT if ( a [ i ] [ j ] == a [ i + 1 ] [ j ] ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT new_prefix = a [ i ] [ 0 : j + 1 ] NEW_LINE if ( len ( temp_prefix ) > len ( new_prefix ) ) : NEW_LINE INDENT res [ ind ] = temp_prefix NEW_LINE ind += 1 NEW_LINE DEDENT else : NEW_LINE INDENT res [ ind ] = new_prefix NEW_LINE ind += 1 NEW_LINE DEDENT temp_prefix = a [ i + 1 ] [ 0 : j + 1 ] NEW_LINE DEDENT j = 0 NEW_LINE sec_last = a [ size - 2 ] NEW_LINE last = a [ size - 1 ] NEW_LINE while ( j < min ( len ( sec_last ) - 1 , len ( last ) - 1 ) ) : NEW_LINE INDENT if ( sec_last [ j ] == last [ j ] ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT res [ ind ] = last [ 0 : j + 1 ] NEW_LINE return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT input = [ " zebra " , " dog " , " duck " , " dove " ] NEW_LINE output = uniquePrefix ( input ) NEW_LINE print ( " The ▁ shortest ▁ unique ▁ prefixes ▁ " + " in ▁ sorted ▁ order ▁ are ▁ : ▁ " ) NEW_LINE for i in output : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT