Find shortest unique prefix for every word in a given list | Set 2 (Using Sorting)
Given an array of words, find all shortest unique prefixes to represent each word in the given array. Assume that no word is a prefix of another. Output the shortest unique prefixes in sorted order.
Input : {"zebra", "dog", "duck", "dove"} Output : z, dog, dov, du Explanation: dog => dog dove = dov duck = du z => zebra Input: {"BeginnerBeginner", "Beginnerquiz", "w3wiki"} Output: Beginnerf, Beginnerg, Beginnerq
We have discussed a Trie based approach in the below post.
Find shortest unique prefix for every word in a given list | Set 1 (Using Trie)
In this post, a sorting based approach is discussed. On comparing the string with 2 other most similar strings in the array, we can find its shortest unique prefix. For example, if we sort the array {“zebra”, “dog”, “duck”, “dove”}, we get {“dog”, “dove”, “duck”, “zebra”}. The shortest unique prefix for the string “dove” can be found as:
Compare “dove” to “dog” –> unique prefix for dove is “dov”
Compare “dove” to “duck” –> unique prefix for dove is “do”
Now, the shortest unique prefix for “dove” is the one with greater length between “dov” and “do”. So, it is “dov”.
The shortest unique prefix for the first and last string can be found by comparing them with only 1 most similar neighbor on right and left, respectively.
We can sort the array of strings and keep on doing this for every string of the array.
Implementation:
C++
// C++ program to print shortest unique prefixes // for every word. #include <bits/stdc++.h> using namespace std; vector<string> uniquePrefix(vector<string> &a) { int size = a.size(); /* create an array to store the results */ vector<string> res(size); /* sort the array of strings */ sort(a.begin(), a.end()); /* compare the first string with its only right neighbor */ int j = 0; while (j < min(a[0].length() - 1, a[1].length() - 1)) { if (a[0][j] == a[1][j]) j++; else break ; } int ind = 0; res[ind++] = a[0].substr(0, j + 1); /* Store the unique prefix of a[1] from its left neighbor */ string temp_prefix = a[1].substr(0, j + 1); for ( int i = 1; i < size - 1; i++) { /* compute common prefix of a[i] unique from its right neighbor */ j = 0; while (j < min(a[i].length() - 1, a[i + 1].length() - 1)) { if (a[i][j] == a[i + 1][j]) j++; else break ; } string new_prefix = a[i].substr(0, j + 1); /* compare the new prefix with previous prefix */ if (temp_prefix.length() > new_prefix.length()) res[ind++] = temp_prefix; else res[ind++] = new_prefix; /* store the prefix of a[i+1] unique from its left neighbour */ temp_prefix = a[i + 1].substr(0, j + 1); } /* compute the unique prefix for the last string in sorted array */ j = 0; string sec_last = a[size - 2]; string last = a[size - 1]; while (j < min(sec_last.length() - 1, last.length() - 1)) { if (sec_last[j] == last[j]) j++; else break ; } res[ind] = last.substr(0, j + 1); return res; } // Driver Code int main() { vector<string> input = { "zebra" , "dog" , "duck" , "dove" }; vector<string> output = uniquePrefix(input); cout << "The shortest unique prefixes in sorted order are : \n" ; for ( auto i : output) cout << i << ' ' ; return 0; } // This code is contributed by // sanjeev2552 |
Java
// Java program to print shortest unique prefixes // for every word. import java.io.*; import java.util.*; class GFG { public String[] uniquePrefix(String[] a) { int size = a.length; /* create an array to store the results */ String[] res = new String[size]; /* sort the array of strings */ Arrays.sort(a); /* compare the first string with its only right neighbor */ 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 ); /* Store the unique prefix of a[1] from its left neighbor */ String temp_prefix = a[ 1 ].substring( 0 , j+ 1 ); for ( int i = 1 ; i < size- 1 ; i++) { /* compute common prefix of a[i] unique from its right neighbor */ 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 ); /* compare the new prefix with previous prefix */ if (temp_prefix.length() > new_prefix.length() ) res[ind++] = temp_prefix; else res[ind++] = new_prefix; /* store the prefix of a[i+1] unique from its left neighbour */ temp_prefix = a[i+ 1 ].substring( 0 , j+ 1 ); } /* compute the unique prefix for the last string in sorted array */ 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; } /* Driver Function to test other function */ 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] + " " ); } } |
Python3
# Python3 program to print shortest unique prefixes # for every word. def uniquePrefix(a): size = len (a) # Create an array to store the results res = [ 0 ] * (size) # Sort the array of strings */ a = sorted (a) # Compare the first with its only right # neighbor j = 0 while (j < min ( len (a[ 0 ]) - 1 , len (a[ 1 ]) - 1 )): if (a[ 0 ][j] = = a[ 1 ][j]): j + = 1 else : break ind = 0 res[ind] = a[ 0 ][ 0 :j + 1 ] ind + = 1 # Store the unique prefix of a[1] # from its left neighbor temp_prefix = a[ 1 ][ 0 :j + 1 ] for i in range ( 1 , size - 1 ): # Compute common prefix of a[i] unique from # its right neighbor j = 0 while (j < min ( len (a[i]) - 1 , len (a[i + 1 ]) - 1 )): if (a[i][j] = = a[i + 1 ][j]): j + = 1 else : break new_prefix = a[i][ 0 :j + 1 ] # Compare the new prefix with previous prefix if ( len (temp_prefix) > len (new_prefix)): res[ind] = temp_prefix ind + = 1 else : res[ind] = new_prefix ind + = 1 # Store the prefix of a[i+1] unique from its # left neighbour temp_prefix = a[i + 1 ][ 0 :j + 1 ] # Compute the unique prefix for the last # in sorted array j = 0 sec_last = a[size - 2 ] last = a[size - 1 ] while (j < min ( len (sec_last) - 1 , len (last) - 1 )): if (sec_last[j] = = last[j]): j + = 1 else : break res[ind] = last[ 0 :j + 1 ] return res # Driver Code if __name__ = = '__main__' : input = [ "zebra" , "dog" , "duck" , "dove" ] output = uniquePrefix( input ) print ( "The shortest unique prefixes " + "in sorted order are : " ) for i in output: print (i, end = " " ) # This code is contributed by mohit kumar 29 |
C#
// C# program to print shortest unique prefixes // for every word. using System; class GFG { public String[] uniquePrefix(String[] a) { int size = a.Length; /* create an array to store the results */ String[] res = new String[size]; /* sort the array of strings */ Array.Sort(a); /* compare the first string with its only right neighbor */ int j = 0; while (j < Math.Min(a[0].Length - 1, a[1].Length - 1)) { if (a[0][j] == a[1][j]) j++; else break ; } int ind = 0; res[ind++] = a[0].Substring(0, j + 1); /* Store the unique prefix of a[1] from its left neighbor */ String temp_prefix = a[1].Substring(0, j + 1); for ( int i = 1; i < size - 1; i++) { /* compute common prefix of a[i] unique from its right neighbor */ j = 0; while (j < Math.Min( a[i].Length - 1, a[i + 1].Length - 1 )) { if (a[i][j] == a[i + 1][j]) j++; else break ; } String new_prefix = a[i].Substring(0, j+1); /* compare the new prefix with previous prefix */ if (temp_prefix.Length > new_prefix.Length ) res[ind++] = temp_prefix; else res[ind++] = new_prefix; /* store the prefix of a[i+1] unique from its left neighbour */ temp_prefix = a[i+1].Substring(0, j+1); } /* compute the unique prefix for the last string in sorted array */ 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[j] == last[j]) j++; else break ; } res[ind] = last.Substring(0, j+1); return res; } /* Driver code */ public static void Main(String[] args) { GFG gfg = new GFG(); String[] input = { "zebra" , "dog" , "duck" , "dove" }; String[] output = gfg.uniquePrefix(input); Console.WriteLine( "The shortest unique prefixes" + " in sorted order are :" ); for ( int i = 0; i < output.Length; i++) Console.Write( output[i] + " " ); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript code for the above approach function uniquePrefix(a) { let size = a.length; /* create an array to store the results */ let res = new Array(size); /* sort the array of lets */ a.sort(); /* compare the first let with its only right neighbor */ let 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 ; } let ind = 0; res[ind++] = a[0].substring(0, j+1); /* Store the unique prefix of a[1] from its left neighbor */ let temp_prefix = a[1].substring(0, j+1); for (let i = 1; i < size-1; i++) { /* compute common prefix of a[i] unique from its right neighbor */ 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 ; } let new_prefix = a[i].substring(0, j+1); /* compare the new prefix with previous prefix */ if (temp_prefix.length > new_prefix.length ) res[ind++] = temp_prefix; else res[ind++] = new_prefix; /* store the prefix of a[i+1] unique from its left neighbour */ temp_prefix = a[i+1].substring(0, j+1); } /* compute the unique prefix for the last let in sorted array */ j = 0; let sec_last = a[size-2] ; let 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; } // Driver Code let input = [ "zebra" , "dog" , "duck" , "dove" ]; let output = uniquePrefix(input); document.write( "The shortest unique prefixes" + " in sorted order are :" + "<br/>" ); for (let i=0; i < output.length; i++) document.write( output[i] + " " ); // This code is contributed by sanjoy_62. </script> |
The shortest unique prefixes in sorted order are : dog dov du z
Another Python approach:
If we want to output the prefixes as the order of strings in the input array, we can store the string and its corresponding index in the hashmap. While adding the prefix to the result array, we can get the index of the corresponding string from the hashmap and add the prefix to that index.
Implementation:
C++
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int main() { string a[] = { "dogs" , "dove" , "duck" , "zebra" }; vector<string> r; // vector to store the shortest unique prefix of each string int j = 0; // Find the common prefix of the first two strings while (j < min(a[0].length(), a[1].length())) { if (a[0][j] == a[1][j]) { j++; } else { break ; } } // Add the prefix to the result vector r.push_back(a[0].substr(0, j+1)); string x = a[1].substr(0, j+1); // Find the common prefix of each pair of adjacent strings for ( int i = 1; i < sizeof (a) / sizeof (a[0]) - 1; i++) { j = 0; while (j < min(a[i].length(), a[i+1].length())) { if (a[i][j] == a[i+1][j]) { j++; } else { break ; } } string y = a[i].substr(0, j+1); // Add the shorter prefix to the result vector if (x.length() > y.length()) { r.push_back(x); } else { r.push_back(y); } x = a[i+1].substr(0, j+1); } // Find the common prefix of the last two strings j = 0; string l = a[ sizeof (a)/ sizeof (a[0])-2]; string k = a[ sizeof (a)/ sizeof (a[0])-1]; while (j < min(l.length(), k.length())) { if (l[j] == k[j]) { j++; } else { break ; } } // Add the prefix to the result vector r.push_back(k.substr(0, j+1)); // Print the result vector cout << "The shortest unique prefixes are: " ; for (string prefix : r) { cout << prefix << " " ; } return 0; } |
Java
// Java program to print shortest unique prefix for every word in a list import java.util.ArrayList; import java.util.List; public class ShortestUniquePrefix { public static void main(String[] args) { String[] a = { "dogs" , "dove" , "duck" , "zebra" }; List<String> r = new ArrayList<>(); int j = 0 ; while (j < Math.min(a[ 0 ].length(), a[ 1 ].length())) { if (a[ 0 ].charAt(j) == a[ 1 ].charAt(j)) { j += 1 ; } else { break ; } } r.add(a[ 0 ].substring( 0 , j + 1 )); String x = a[ 1 ].substring( 0 , j + 1 ); for ( int i = 1 ; i < a.length - 1 ; i++) { j = 0 ; while (j < Math.min(a[i].length(), a[i + 1 ].length())) { if (a[i].charAt(j) == a[i + 1 ].charAt(j)) { j += 1 ; } else { break ; } } String y = a[i].substring( 0 , j + 1 ); if (x.length() > y.length()) { r.add(x); } else { r.add(y); } x = a[i + 1 ].substring( 0 , j + 1 ); } j = 0 ; String l = a[a.length - 2 ]; String k = a[a.length - 1 ]; while (j < Math.min(l.length(), k.length())) { if (l.charAt(j) == k.charAt(j)) { j += 1 ; } else { break ; } } r.add(k.substring( 0 , j + 1 )); System.out.println( "The shortest unique prefixes are: " ); for (String prefix : r) { System.out.print(prefix + " " ); } } } |
Python3
#Python program to print shortest unique prefix for every word in a list a = [ 'dogs' , 'dove' , 'duck' , 'zebra' ] r = [] j = 0 while (j< min ( len (a[ 0 ]), len (a[ 1 ]))): if (a[ 0 ][j] = = a[ 1 ][j]): j + = 1 else : break i = 0 r.append(a[ 0 ][ 0 :j + 1 ]) x = a[ 1 ][ 0 :j + 1 ] for i in range ( 1 , len (a) - 1 ): j = 0 while (j< min ( len (a[i]), len (a[i + 1 ]))): if a[i][j] = = a[i + 1 ][j]: j + = 1 else : break y = a[i][ 0 :j + 1 ] if ( len (x)> len (y)): r.append(x) else : r.append(y) x = a[i + 1 ][ 0 :j + 1 ] j = 0 l = a[ len (a) - 2 ] k = a[ len (a) - 1 ] while (j< min ( len (l), len (k))): if ( l[j] = = k[j]): j + = 1 else : break r.append(k[ 0 :j + 1 ]) print ( "The shortest unique prefixes are :" ) for i in range ( 0 , len (r)): print (r[i],end = ' ' ) #This code is contributed by Saahith Reddy |
Javascript
// Javascript program to print shortest unique prefix for every word in a list let a=[ 'dogs' , 'dove' , 'duck' , 'zebra' ]; let r=[]; let j=0; while (j<Math.min(a[0].length, a[1].length)){ if (a[0][j]===a[1][j]){ j+=1; } else { break ; } } r.push(a[0].substring(0, j+1)); let x=a[1].substring(0, j+1); for (let i=1; i<a.length-1; i++){ j=0; while (j<Math.min(a[i].length, a[i+1].length)){ if (a[i][j]===a[i+1][j]){ j+=1; } else { break ; } } let y=a[i].substring(0, j+1); if (x.length>y.length){ r.push(x); } else { r.push(y); } x=a[i+1].substring(0, j+1); } j=0; let l=a[a.length-2]; let k=a[a.length-1]; while (j<Math.min(l.length, k.length)){ if (l[j]===k[j]){ j+=1; } else { break ; } } r.push(k.substring(0, j+1)); console.log( "The shortest unique prefixes are :" ); for (let i=0; i<r.length; i++){ process.stdout.write(r[i] + ' ' ); } // This code is contributed by adityashatmfh |
C#
// C# program to print shortest unique prefix for every word // in a list using System; using System.Collections.Generic; public class ShortestUniquePrefix { static public void Main() { string [] a = { "dogs" , "dove" , "duck" , "zebra" }; List< string > r = new List< string >(); int j = 0; while (j < Math.Min(a[0].Length, a[1].Length)) { if (a[0][j] == a[1][j]) { j += 1; } else { break ; } } r.Add(a[0].Substring(0, j + 1)); string x = a[1].Substring(0, j + 1); for ( int i = 1; i < a.Length - 1; i++) { j = 0; while (j < Math.Min(a[i].Length, a[i + 1].Length)) { if (a[i][j] == a[i + 1][j]) { j += 1; } else { break ; } } string y = a[i].Substring(0, j + 1); if (x.Length > y.Length) { r.Add(x); } else { r.Add(y); } x = a[i + 1].Substring(0, j + 1); } j = 0; string l = a[a.Length - 2]; string k = a[a.Length - 1]; while (j < Math.Min(l.Length, k.Length)) { if (l[j] == k[j]) { j += 1; } else { break ; } } r.Add(k.Substring(0, j + 1)); Console.WriteLine( "The shortest unique prefixes are: " ); foreach ( string prefix in r) { Console.Write(prefix + " " ); } } } |
The shortest unique prefixes are : dog dov du z
For a more efficient solution, we can use Trie as discussed in this post.
Contact Us