26
\$\begingroup\$

Given a list of strings s_0, s_1, ..., s_n find the shortest string S that contains each of s_0, s_1, ..., s_n as a substring.

Examples:

  • S('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')='SEDOLOREMAGNAD'
  • S('ABCDE', 'BCD', 'C')='ABCDE'

Write the shortest program (or function) that solves this problem. You can represent strings as arrays or lists of characters/integers if you want. Standard libraries are OK. For input/output you can use whatever is more convenient: STDIN/STDOUT, user prompt, parameter/return value of a function etc.

Performance is not critical - let's say, for an input of total length < 100 characters the result must be computed in < 10 second on average modern hardware.

\$\endgroup\$
  • 3
    \$\begingroup\$ +1 Nice question. I suggest you include some additional examples of expected outcomes so people can easily judge whether the submissions are able to handle a variety of cases. \$\endgroup\$ – DavidC May 9 '13 at 17:12
  • \$\begingroup\$ How should input/output be handled? Should the result be printed or returned from a function? \$\endgroup\$ – flornquake May 9 '13 at 17:31
  • \$\begingroup\$ so, no "for every string, if it contains all of ..., return it " is not a valid solution? \$\endgroup\$ – John Dvorak May 9 '13 at 18:55
  • \$\begingroup\$ I doubt there's going to be an answer. This question might fit on Stack Overflow (without the code-golf part) quite well. \$\endgroup\$ – John Dvorak May 9 '13 at 20:35
8
\$\begingroup\$

Python 2, 170 153/157/159

Shortened thanks to some of Baptiste's ideas.

from itertools import*
print min((reduce(lambda s,w:(w+s[max(i*(s[:i]==w[-i:])for i in range(99)):],s)[w in s],p)
for p in permutations(input())),key=len)

The second line break is not needed.

Input: 'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'
Output: SEDOLOREMAGNAD

Even with long input strings, this runs in less than 2 seconds if there are at most 7 input strings (as is the case in the example given, which runs in 1.7 1.5 seconds on my machine). With 8 or more input strings, however, it takes more than 10 seconds, since the time complexity is O(n!).

As Baptiste pointed out, range(99) needs to be replaced with range(len(w)) if arbitrary input lengths should be supported (making the total length of the code 157 characters). If empty input strings should be supported, it has to be changed to range(len(w)+1). I think range(99) works correctly for any total input length less than 200, though.

More tests:

>>> "AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"
SEDOLOREMAGNAD

>>> 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', 'abcdefghijklmnopqrstuvw
... xyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstu
... vwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 'ZOOM', 'aZ', 'Za', 'ZA'
aZABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZOOM
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Mathematica 337 418 372

After trying unsuccessfully to implement using Mathematica's LongestCommonSubsequencePositions, I turned to pattern matching.

v=Length;
p[t_]:=Subsets[t,{2}];
f[w_]:=Module[{c,x,s=Flatten,r={{a___,Longest[y__]},{y__,b___}}:>{{a,y},{y,b},{y},{a,y,b}}},
c=p@w;
x=SortBy[Cases[s[{#/.r,(Reverse@#)/.r}&/@c,1],{_,_,_,_}],v[#[[3]]]&][[-1]];
Append[Complement[w,{x[[1]],x[[2]]}],x[[4]]]]

g[r_]:=With[{h=Complement[r,Cases[Join[p@r,p@Reverse@r],y_/;!StringFreeQ@@y:>y[[2]]]]},
FixedPoint[f,Characters/@h,v@h-1]<>""]

The pattern-matching rule,

r={{a___,Longest[y__]},{y__,b___}}:> {{a,y},{y,b},{y},{a,y,b}}},

takes an ordered pair of words (represented as lists of characters) and returns: (1) the words,{a,y} and {y,b} followed by (2) the common substring,y, that links the end of one word with the beginning of the other word, and, finally, the combined word {a,y,b} that will replace the input words. See Belisarius for a related example: https://mathematica.stackexchange.com/questions/6144/looking-for-longest-common-substring-solution

Three consecutive underscore characters signify that the element is a sequence of zero or more characters.

Reverse is employed later to ensure that both orders are tested. Those pairs that share linkable letters are returned unchanged and ignored.

Edit:

The following removes from the list words that are "buried" (i.e. fully contained) in another word, (in response to @flornquake's comment).

h=Complement[r,Cases[Join[p@r,p@Reverse@r],x_/;!StringFreeQ@@x:> x[[2]]]]

Example:

 {{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}} /. r

returns

{{"D", "O", "L", "O", "R", "E"}, {"L", "O", "R", "E", "M"}, {"L", "O", "R", "E"}, {"D", "O", "L", "O", "R", "E", "M"}}


Usage

g[{"LOREM", "ORE", "R"}]

AbsoluteTiming[g[{"AD", "DO", "DOLOR", "DOLORE", "LOREM", "MAGNA", "SED", "ORE",  "R"}]]

"LOREM"

{0.006256, "SEDOLOREMAGNAD"}

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Does this work for input "LOREM", "ORE", "R"? \$\endgroup\$ – flornquake May 9 '13 at 23:55
  • \$\begingroup\$ (I.e., does it produce the correct output "LOREM"?) \$\endgroup\$ – flornquake May 10 '13 at 0:04
  • \$\begingroup\$ @flornquake. Nice catch. I addressed it in the current version. I hope I haven't missed any other cases. Thanks. \$\endgroup\$ – DavidC May 10 '13 at 0:44
  • \$\begingroup\$ Nothing but the best! \$\endgroup\$ – DavidC May 11 '13 at 14:21
3
\$\begingroup\$

GolfScript, 66 characters

{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=

Quite short, but due to exponential time complexity (and GolfScript) really slow, it breaks the 10 seconds time limit.

Examples:

['LOREM' 'DOLOR' 'SED' 'DO' 'MAGNA' 'AD' 'DOLORE']
{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=
# => SEDOLOREMAGNAD

['AB' 'BC' 'CA' 'BCD' 'CDE']
{.,1>{.`{[1$]-s:h;.,),\`{:g<`{\+.g?0<{;}*}+h%~}+/}+%.&}*}:s~{,}$0=
# => CABCDE
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python 2, 203 187 200

from itertools import permutations as p
def n(c,s=''):
 for x in c:s+=x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if s.endswith(l)),0):]
 return s
print min(map(n,p(input())),key=len)

Input: ['LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE']
Output: SEDOLOREMAGNAD

Edit

Using reduce and some dirty import trickery, I can reduce this further (and to one line only!):

print min((reduce(lambda a,x:a+x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],P,'')for P in __import__('itertools').permutations(input())),key=len)

Edit 2

As flornquake noted, this gives incorrect results when one word is contained in another. The fix for this adds another 13 chars:

print min((reduce(lambda a,x:a+(x[next((i+1 for i,l in [(j,x[:j+1])for j in range(len(x))][::-1]if a.endswith(l)),0):],'')[x in a],P,'')for P in __import__('itertools').permutations(input())),key=len)

Here's the cleaned up version:

from itertools import permutations

def solve(*strings):
    """
    Given a list of strings, return the shortest string that contains them all.
    """
    return min((simplify(p) for p in permutations(strings)), key=len)

def prefixes(s):
    """
    Return a list of all the prefixes of the given string (including itself),
    in ascending order (from shortest to longest).
    """
    return [s[:i+1] for i in range(len(s))]
    return [(i,s[:i+1]) for i in range(len(s))][::-1]

def simplify(strings):
    """
    Given a list of strings, concatenate them wile removing overlaps between
    successive elements.
    """
    ret = ''
    for s in strings:
        if s in ret:
            break
        for i, prefix in reversed(list(enumerate(prefixes(s)))):
            if ret.endswith(prefix):
                ret += s[i+1:]
                break
        else:
            ret += s
    return ret

print solve('LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE')

It's possible to shave off a few characters at the cost of theoretical correctness by using range(99) instead of range(len(x)) (credits to flornquake for thinking of this one).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ If you're willing to sacrifice correctness then you might as well use the greedy approach or the polynomial approximation factor of 2 approach. \$\endgroup\$ – Peter Taylor May 10 '13 at 14:33
  • \$\begingroup\$ Nice solution! You need to check if new words are already in the superstring, though: 'LOREM', 'ORE', 'R' incorrectly produces the output LOREMORER. \$\endgroup\$ – flornquake May 10 '13 at 20:19
  • \$\begingroup\$ @flornquake Good catch. I managed to fix it but it adds 13 characters. \$\endgroup\$ – Baptiste M. May 11 '13 at 8:40
1
\$\begingroup\$

Python, 144 chars

S=lambda A,s:min(S(A-set([a]),s+a[i:])for a in A for i in range(len(a)+1)if i==0 or s[-i:]==a[:i])if A else(len(s),s)
T=lambda L:S(set(L),'')[1]

S takes a set of words A that still need placing and a string s containing words placed so far. We pick a remaining word a from A and overlap it from 0 to len(a) characters with the end of s.

Takes only about 0.15 seconds on the given example.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Really nice! But like some other solutions, this doesn't work for input like ['LOREM', 'ORE', 'R']. I've taken the liberty to fix that and golf your solution some more: S=lambda A,s='':A and min((S(A-{a},(s+a[max(i*(s[-i:]==a[:i])for i in range(len(a))):],s)[a in s])for a in A),key=len)or s (a second line is not needed). Usage: S({'LOREM', 'DOLOR', 'SED', 'DO', 'MAGNA', 'AD', 'DOLORE'}) returns 'SEDOLOREMAGNAD'. \$\endgroup\$ – flornquake May 11 '13 at 16:26
0
\$\begingroup\$

Haskell, 121

import Data.List
a p []=[(length p,p)]
a p s=[r|w<-s,t<-tails w,isInfixOf w$p++t,r<-a(p++t)(s\\[w])]
s=snd.minimum.a ""

Minus two if the function doesn't need to be bound to a name

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.