OrderedSuperString
SRM 409 · 2008-07-10 · by slex
Problem Statement
A string X is an ordered superstring of the
- Each element of words is a substring of X.
- There exists a sequence of indices x_1 <= x_2 <= ... <= x_n, where n is the number of elements in words. For each element k of words, where k is a 1-based index, there is an occurrence of words[k] that starts at the x_k-th letter of X.
Given a
Constraints
- words will contain between 1 and 50 elements, inclusive.
- Each element of words will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
{"abc","ca"}
Returns: 4
This is the example from the problem statement. The shortest ordered superstring is "abca". The sequence of indices is {0, 2}. There is an occurrence of "abc" starting at character 0 of "abca", and there is an occurrence of "ca" starting at character 2 of "abca".
{"a","a","b","a"}
Returns: 3
Although the given words are all substrings of "ab", they do not appear in the proper order. The shortest ordered superstring is "aba".
{"abcdef", "ab","bc", "de","ef"}
Returns: 6
{"ab","bc", "de","ef","abcdef"}
Returns: 12
{"a"}
Returns: 1
Submissions are judged against all 166 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class OrderedSuperString with a public method int getLength(vector<string> words) · 166 test cases · 2 s / 256 MB per case