TopCoder problem "OrderedSuperString" used in SRM 409 (Division I Level One , Division II Level Two)



Problem Statement

    

A string X is an ordered superstring of the String[] words if

  • 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.
For example "abca" is an ordered superstring of {"abc", "ca"}, but "cabc" is not.

Given a String[] words, return the length of its shortest ordered superstring.

 

Definition

    
Class:OrderedSuperString
Method:getLength
Parameters:String[]
Returns:int
Method signature:int getLength(String[] words)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{"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".
1)
    
{"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".
2)
    
{"abcdef", "ab","bc", "de","ef"}
Returns: 6
3)
    
{"ab","bc", "de","ef","abcdef"}
Returns: 12

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9823

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12181&pm=9823

Writer:

slex

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Greedy, String Manipulation