Find shortest unique prefix for every word in a given list | Set 2 ( Using Sorting ) | Java program to print shortest unique prefixes for every word . ; create an array to store the results ; sort the array of strings ; compare the first string 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 string in sorted array ; Driver Function to test other function
import java . io . * ; import java . util . * ; class GFG { public String [ ] uniquePrefix ( String [ ] a ) { int size = a . length ; String [ ] res = new String [ size ] ; Arrays . sort ( a ) ; int j = 0 ; while ( j < Math . min ( a [ 0 ] . length ( ) - 1 , a [ 1 ] . length ( ) - 1 ) ) { if ( a [ 0 ] . charAt ( j ) == a [ 1 ] . charAt ( j ) ) j ++ ; else break ; } int ind = 0 ; res [ ind ++ ] = a [ 0 ] . substring ( 0 , j + 1 ) ; String temp_prefix = a [ 1 ] . substring ( 0 , j + 1 ) ; for ( int i = 1 ; i < size - 1 ; i ++ ) { j = 0 ; while ( j < Math . min ( a [ i ] . length ( ) - 1 , a [ i + 1 ] . length ( ) - 1 ) ) { if ( a [ i ] . charAt ( j ) == a [ i + 1 ] . charAt ( j ) ) j ++ ; else break ; } String new_prefix = a [ i ] . substring ( 0 , j + 1 ) ; if ( temp_prefix . length ( ) > new_prefix . length ( ) ) res [ ind ++ ] = temp_prefix ; else res [ ind ++ ] = new_prefix ; temp_prefix = a [ i + 1 ] . substring ( 0 , j + 1 ) ; } j = 0 ; String sec_last = a [ size - 2 ] ; String last = a [ size - 1 ] ; while ( j < Math . min ( sec_last . length ( ) - 1 , last . length ( ) - 1 ) ) { if ( sec_last . charAt ( j ) == last . charAt ( j ) ) j ++ ; else break ; } res [ ind ] = last . substring ( 0 , j + 1 ) ; return res ; } public static void main ( String [ ] args ) { GFG gfg = new GFG ( ) ; String [ ] input = { " zebra " , " dog " , " duck " , " dove " } ; String [ ] output = gfg . uniquePrefix ( input ) ; System . out . println ( " The ▁ shortest ▁ unique ▁ prefixes " + " ▁ in ▁ sorted ▁ order ▁ are ▁ : " ) ; for ( int i = 0 ; i < output . length ; i ++ ) System . out . print ( output [ i ] + " ▁ " ) ; } }