WordAbbreviation
SRM 402 · 2008-05-24 · by srbga
SRM 402 · 2008-05-24 · by srbga · Simple Search, Iteration, String Manipulation
Problem Statement
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.
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)
{"oimohaciiocqmha","mmhjopmkaoebhpcjeraaicconekaoieioaoiafhbho","rkka","rjkjchklpfjqgknhjqpaqqcdmfqekkairl","baelphgogljohqhngkhidekbogbjmbojpglnp","ejefeldafnkkgbjqrml","rqdabeqmrfbaangiffdrpfkmmelcq","qmhrlcpnebom","jbihapdqdpmocnqmrakmfp","lgfjldrobjcekjkplr","ekbaabijrpjcripahaifgddkmnqkeca","jdolnpidqlea","nplhnbigbdnanonnh","pecpagclrg","hinonemgqhgljkiqjdfbrlnoobmqrgjfmaohkk","iddefohggnndjeqmmngnocnfohlkinfoicqmllpkiij","fplregrinhlamkdoqefamfcnihiccacbhjpemaeir","lij","obmfpgmqineepchoaamafdpqdjkbommpoelil","jj","bibijaclmffq","legmlhgqi"}
Returns: {"oi", "m", "rk", "rj", "ba", "ej", "rq", "q", "jb", "lg", "ek", "jd", "n", "p", "h", "i", "f", "li", "ob", "jj", "bi", "le" }
4)
{"iiddfphifrfhinmqinhaklfpljoc","hmnnbmcnnqhnedqmlfikmcrjcfpmomqfjflejderokpafidrgr","kjelckgqljdgnnjajffffnqkrlopnd","dknhedbbkjmhdpabdlerrapijprjooajjhkaripoceadfcmhin","ekfbffkpndilijnfroloqgoorcgb","gobj","omnbnnfmrcfniblqmbbeigkipqfjicdihbpgdepjpakmicla","acpraengllrjlhl","knmgkjnklrarngdnra","bhkin","jggoflofhccnqcrpohh","hmphnj","npffrlickgldrfhejfpgbfqjarlr"}
Returns: {"i", "hmn", "kj", "d", "e", "g", "o", "a", "kn", "b", "j", "hmp", "n" }
Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class WordAbbreviation with a public method vector<string> getAbbreviations(vector<string> words) · 115 test cases · 2 s / 256 MB per case