JoinedString
SRM 302 · 2006-05-11 · by Andrew_Lazarev
SRM 302 · 2006-05-11 · by Andrew_Lazarev · Dynamic Programming, String Manipulation
Problem Statement
Problem Statement
You are given a String[] words. Return the shortest String that contains all the words as substrings. If there are several possible answers, return the one that comes first lexicographically.
Constraints
- words will contain between 1 and 12 elements, inclusive.
- Each element of words will contain between 1 and 50 characters, inclusive.
- Each element of words will consist of only uppercase letters ('A'-'Z').
Examples
0)
{"BAB", "ABA"}
Returns: "ABAB"
There are two strings of length 4 that contain both given words: "ABAB" and "BABA". "ABAB" comes earlier lexicographically.
1)
{"ABABA", "AKAKA", "AKABAS", "ABAKA"}
Returns: "ABABAKAKABAS"
2)
{"AAA","BBB", "CCC", "ABC", "BCA", "CAB"}
Returns: "AAABBBCABCCC"
3)
{"OFG", "SDOFGJTILM", "KBWNF", "YAAPO", "AWX", "VSEAWX", "DOFGJTIL", "YAA"}
Returns: "KBWNFSDOFGJTILMVSEAWXYAAPO"
4)
{"NVCSKFLNVS", "HUFSPMRI", "FLNV", "KMQD", "RPJK", "NVSQORP", "UFSPMR", "AIHUFSPMRI"}
Returns: "AIHUFSPMRINVCSKFLNVSQORPJKMQD"
Submissions are judged against all 145 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class JoinedString with a public method string joinWords(vector<string> words) · 145 test cases · 2 s / 256 MB per case