StickedWords | Topcoder Archive

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 String ("") if such a line cannot be constructed.

Definition

Class:: StickedWords
Method:: constructLine
Parameters:: String[], int
Returns:: String
Method signature:: String constructLine(String[] dict, int len)
(be sure your method is public)

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.

Examples

```
{"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"}

Returns: ""

{"aba", "aac", "czz"}

Returns: "abababaaczz"

{"aarb", "bcb", "bbd", "dzz"}

Returns: "aarbcbcbcbcbbdzz"

{"abd", "dgga", "abdg", "gga", "gg", "gaader"}

Returns: "abdggabdggabdggabdgaader"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.