Problem Statement
A String S is an interspersal of a set of Strings W, if W is a set of disjoint subsequences of S which cover S. Less formally, S can be formed from W by partitioning each member of W into substrings, then concatenating all the substrings, while maintaining the order of the substrings within each element of W. For example, if W contains the strings {"DESIGN", "ALGORITHM", "MARATHON"}, then one possible interspersal would be "ADELGMAORARISIGNTHMTHON", formed as shown below.
DE SIGN
A LG O RI THM
MA RA THON
-----------------------
ADELGMAORARISIGNTHMTHON
Given a String[] W, return the lexicographically minimum interspersal of the Strings in W
Definition
- Class:
- StringInterspersal
- Method:
- minimum
- Parameters:
- String[]
- Returns:
- String
- Method signature:
- String minimum(String[] W)
- (be sure your method is public)
Notes
- The lexicographically minimum of two Strings is the one with the alphabetically earlier character at the first position at which they differ.
- The return String will contain no more than 1000 characters.
Constraints
- W will contain between 1 and 20 elements, inclusive.
- Each element of W will contain between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
Examples
{"DESIGN","ALGORITHM","MARATHON"}Returns: "ADELGMAORARISIGNTHMTHON"
The example from the problem statement.{"TOMEK","PETR","ACRUSH","BURUNDUK","KRIJGERTJE"}Returns: "ABCKPERIJGERRTJETOMEKTRURUNDUKUSH"
{"CCCA","CCCB","CCCD","CCCE"}Returns: "CCCACCCBCCCCCCDE"
{"BKSDSOPTDD","DDODEVNKL","XX","PODEEE","LQQWRT"}Returns: "BDDKLODEPODEEEQQSDSOPTDDVNKLWRTXX"
{"TOPCODER","BETFAIR","NSA","BT","LILLY"}Returns: "BBELILLNSATFAIRTOPCODERTY"
{"QITHSQARQV","BYLHVGMLRY","LKMAQTJEAM","AQYICVNIKK","HKGZZFFEWC"}Returns: "ABHKGLKMAQIQQTHSQARQTJEAMVYICVNIKKYLHVGMLRYZZFFEWC"
{"XHCYBTUQUW","EKBISADSSN","LOOISPOFAK","MIXBDHPJUQ","BNMNDHMOTC"}Returns: "BEKBILMINMNDHMOOIOSADSPOFAKSSNTCXBDHPJUQXHCYBTUQUW"
Back to all problems