StickedWords
SRM 291 · 2006-02-21 · by Andrew_Lazarev
Problem Statement
We have a dictionary of words dict, and we are writing words down in a single line using the following rules. The first written word can be any word from dict. Each subsequent written word must start with the same letter as the last letter of the previous written word, and that shared letter is only written once (see examples). Only words from dict can be used, but each word can be used an unlimited number of times.
Using the rules above, construct the lexicographically earliest line with length greater than or equal to len characters. Return an empty
Constraints
- dict will contain between 1 and 50 elements, inclusive.
- Each element of dict will contain between 2 and 50 characters, inclusive.
- Each element of dict will contain only lowercase letters ('a'-'z').
- len will be between 1 and 2500, inclusive.
{"salad", "sandwich", "hamburger", "rings"}
35
Returns: "hamburgeringsandwichamburgeringsalad"
The first word in the line is "hamburger". The next word must start with the letter 'r', so we write "rings". Notice that we only write the shared 'r' once, so at this point, the line is "hamburgerings". The rest of the words, in order, are: "sandwich", "hamburger", "rings", and "salad". The resulting line is 36 characters long, and is the lexicographically earliest possible line containing at least 35 characters.
{"salad", "hamburger", "rings"}
35
Returns: ""
{"aba", "aac", "czz"}
10
Returns: "abababaaczz"
{"aarb", "bcb", "bbd", "dzz"}
15
Returns: "aarbcbcbcbcbbdzz"
{"abd", "dgga", "abdg", "gga", "gg", "gaader"}
22
Returns: "abdggabdggabdggabdgaader"
Submissions are judged against all 243 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StickedWords with a public method string constructLine(vector<string> dict, int len) · 243 test cases · 2 s / 256 MB per case