Explore BrainMass

Shortest Prefixes

Shortest Prefixes

Input: Prefix .in
Output: Prefix .out

A prefix of a string is a substring string at the beginning of the given string. The prefixes of "carbon" are: "c", "ca", car", "carb", "carbo", and "carbon". Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, "carbohydrate "is commonly abbreviated by "carb". In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, "carbohydrate" can be abbreviated to "carboh", but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the list that begin with "carbo".

An exact match will override a prefix match. For example, the prefix "car" matches the given word "car" exactly. Therefore, it is understood without ambiguity that "car" is an abbreviation for "car", not for "carriage" or any of the other words in the list that begins with "car"

"" Input ""

The input file contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.

"" Output ""

The output file contains the same number of lines as the input file. Each line of the output file contains the word from the corresponding line of the input file, followed by one blank space; and the shortest prefix that uniquely (without ambiguity) identifies this word.

"" Sample input ""


"" Output for sample input ""

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

Solution Preview


Attached are a few documents related to the solution. The visio has the visual representation of the solution which can be used as reference while going through the write-up. I wasnot sure if you had visio or not, so have converted it into a html format as well.

Solution as follows:

1> Read the file either
a> character by character till end of line (line feed or carriage return is reached) to create the word or
b> read one word and go to the next line.
c> read the complete line as it contains only 1 word.

2> Create a Hash table or Hash Map, which stores the Name - Value pair combination. (As referred in Figure-1)
a> The Name used in this Hash Table would be the Line Number
b> The Value would be the value of the word read in Step 1.

3> Create another Hash table or Hash Map, which will store the Name - Value pair of (As referred in Figure-2)
a> the I/P word, which will be the Name and
b> the Value will be an empty value or null.

4> Create a sorted link list or a ...

Solution Summary

Shortest Prefixes are highlighted.