Shortest Prefixes
Not what you're looking for?
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 ""
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
"" 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
Purchase this Solution
Solution Summary
Shortest Prefixes are highlighted.
Solution Preview
Hello,
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 ...
Purchase this Solution
Free BrainMass Quizzes
C# variables and classes
This quiz contains questions about C# classes and variables.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Word 2010: Table of Contents
Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.