TopCoder problem "WordAbbreviation" used in SRM 402 (Division II Level One)



Problem Statement

    You are given a String[] words, each element of which is a single word. Return a String[] where the i-th element is the abbrevation for the i-th word. The abbreviation for a word is its shortest non-empty prefix that is not a prefix of any other given word. The constraints will guarantee that it is possible to find an abbreviation for all the given words.
 

Definition

    
Class:WordAbbreviation
Method:getAbbreviations
Parameters:String[]
Returns:String[]
Method signature:String[] getAbbreviations(String[] words)
(be sure your method is public)
    
 

Notes

-A string s1 is called a prefix of string s2 if and only if s1 can be obtained by removing zero or more characters from the end of s2.
 

Constraints

-words will contain between 1 and 50 elements, inclusive.
-Each element of words will contain between 1 and 50 characters, inclusive.
-Each element of words will only contain lowercase letters ('a'-'z').
-No element of words will be a prefix of another element of words.
 

Examples

0)
    
{"abc","def","ghi"}
Returns: {"a", "d", "g" }
A single character is enough.
1)
    
{"aaab","aaac","aaad"}
Returns: {"aaab", "aaac", "aaad" }
It's possible that the abbreviation is the same as the original word.
2)
    
{"top","coder","contest"}
Returns: {"t", "cod", "con" }
3)
    
{
 "bababaaaaa",
 "baaabaababa",
 "bbabaaabbaaabbabaabaabbbbbaabb",
 "aaababababbbbababbbaabaaaaaaaabbabbbaaab",
 "baaaaabaababbbaabbbabbababbbabbbbbbbbab"
}
Returns: {"bab", "baaab", "bb", "a", "baaaa" }
4)
    
{"oneword"}
Returns: {"o" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8310

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12174&pm=8310

Writer:

srbga

Testers:

PabloGilberto , Olexiy , ivan_metelsky , Gassa

Problem categories:

Simple Search, Iteration, String Manipulation