19
\$\begingroup\$

Given a string, like potatocarrot, break it into the smallest number of substrings possible. These substrings can consist either be a single character, or one of a list of words passed as input. For example, if [carrot, potato] was the input, the optimal way to break the string up would be [potato][carrot]. If the list was [potat, tatocarr, rot], the optimal way would be [p][o][tatocarr][o][t].

You can take the string in any reasonable format, and the list of substrings in any reasonable format. As for output, any of the following would be examples of allowed output formats:

  • Inserting characters into the string to delimit substrings (e.g., "potato,carrot" or "[potato][carrot]")
  • Delimiting words, but not individual characters (e.g., "po[tatocarr]ot", but not "po,tatocarr,ot")
  • Returning an array of substrings (e.g., ["potato", "carrot"])

You can assume the input strings consist of lowercase letters, and that there won't be duplicates or strings with a length of 0 or 1 in the list of substrings.

This is , so shortest answer (in bytes) per language wins.

Test cases:

STRING          WORDS                   OPTIMAL SOLUTION
potatocarrot    potato, carrot          [potato][carrot]
potatocarrot    pot, tatocarr, rot      [p][o][tatocarr][o][t]
potatocarrot    atocarr, ot             [p][ot][atocarr][ot]
potatocarrot    tatocarr, potato, carr  [potato][carr][o][t]
purpur                                  [p][u][r][p][u][r]
purpur          carrot                  [p][u][r][p][u][r]
purpur          pur                     [pur][pur]
purpur          pu, rp                  [pu][r][pu][r] OR [pu][rp][u][r]
purpur          pu, rp, urp             [pu][r][pu][r] OR [pu][rp][u][r] OR [p][urp][u][r]
todoornottodo   to, do, or, not         [to][do][or][not][to][do]
todoornottodo   tod, nott, door         [t][o][door][nott][o][d][o]
\$\endgroup\$
2
  • \$\begingroup\$ I tried to find out if there are any CJK tokenizer tools (libraries) may be used. But seems failed: All these known tools use something more complex algorithm so I cannot simply import a custom dictionary and invoke the library to finish this question... \$\endgroup\$
    – tsh
    Apr 11 at 10:22
  • \$\begingroup\$ @tsh That's too bad, it sounds like that would have been a pretty interesting and creative answer \$\endgroup\$ Apr 11 at 12:43

8 Answers 8

5
\$\begingroup\$

Python, 82 bytes

f=lambda s,d:s and min([[w,*f(s[len(w):],d)]for w in[*d,*s]if w+"~">s>=w],key=len)

Attempt This Online!

Depth-first search over solution space.

-6 bytes thanks to loopy walt

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -6 I believe. \$\endgroup\$
    – loopy walt
    Apr 10 at 2:18
4
\$\begingroup\$

APL(Dyalog Unicode), 42 bytes SBCS

Assumes index origin 0. Takes the string as right argument ⍵ and the word list as left argument ⍺.

{e⊃⍨⊃⍋≢¨e←d/⍨(1∧.=≢¨∨∊∘⍺)¨d←⊂∘⍵¨~,⍳1+×⍳≢⍵}

Try it on APLgolf!

⍳≢⍵ Indices of the string: 0 1 ... (length-1)
1+× Sign of that incremented: 1 2 2 ... 2 2
,⍳ Indices of an array of that shape, flattened. All these indices have a 0 in the first position and some combination of 1's and 0's after that.
~ Boolean inverse.
d←⊂∘⍵¨ Partition the string according to each of these sequences. This yields a list of all partitions. (Call this d)
≢¨∨∊∘⍺ ¨ For each substring in each partition, take the gcd of its length and the boolean indicating whether it is in the word list. This is only 1 if at least one of the values is 1.
1∧.= For each partition, are all values 1?
e←d/⍨ Only keep partitions where this is the case and call these e.
e⊃⍨⊃⍋≢¨ Pick the partition with minimal length.

\$\endgroup\$
4
\$\begingroup\$

Ruby, 60 53 bytes

->s,l,r=""{s=~/^#{r+="(.|"+l*?|+?)}$/?$~[1..-1]:redo}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Retina, 81 65 bytes

/,;/^+%L$w`\b(\w(\w+)?)(\w*;(?(2).*\b\1\b))
$`$1,$3$'
0G`,;
,;.*

Try it online! Link includes test cases. Explanation:

/,;/^+

Repeat until a complete substring list has been found...

%L$w`\b(\w(\w+)?)(\w*;(?(2).*\b\1\b))

... find all of the leading substrings of the rest of the input that are either a single character or are present in the list of words, ...

$`$1,$3$'

... and create new substring lists containing each of those substrings.

0G`,;
,;.*

Output just the first complete list of substrings.

\$\endgroup\$
2
\$\begingroup\$

Python, 353 348 342 309 bytes

import re,itertools as I
def f(s,a):
 u=[]
 for e in I.permutations(a):
  *r,=s
  for x in e:
   if x in s:
    p=0
    for _ in"_"*s.count(x):
     b=s.index(x,p);p=b+len(x);j=''.join(r[b:p])
     if j.isalpha():r[b]='<'+r[b];r[p-1]+='>'
  u+=''.join(r),
 return min(u,key=lambda x:len(re.sub('<.+?>','',x)))

Attempt This Online!

-5 bytes thanks to ophact

-33 bytes thanks to pxeger

\$\endgroup\$
3
  • \$\begingroup\$ Between d+len(x) and j, remove the newline and whitespace, and place a semicolon instead \$\endgroup\$
    – ophact
    Apr 9 at 18:16
  • \$\begingroup\$ for _ in range(s.count(x)): can be for _ in"_"*s.count(x):. And if'['not in j and']'not in j can be if j.isalpha(). Also, r=[*s] can be *r,=s. Finally, if you switch from using [] to <>, you won't have to escape them in the regular expression and save another 2 bytes \$\endgroup\$
    – pxeger
    Apr 9 at 19:28
  • \$\begingroup\$ b,p=(d:=s.index(x,p)),d+len(x) can be simplified to b=s.index(x,p);p=b+len(x). And sorted(...)[0] can just be min(...). And u+=[''.join(r)] can be u+=''.join(r), \$\endgroup\$
    – pxeger
    Apr 9 at 19:33
2
\$\begingroup\$

JavaScript (ES6),  104 102 97  96 bytes

Expects (word_list)(string). Returns a list of substrings.

a=>g=(s,O=o='',...b)=>[s[O.length],...a].every(e=>e&&g(s,O+e,...b,e))|O!=s||b[o&&o.length]?o:o=b

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python3, 145 bytes:

lambda s,w:min(f(s,w),key=len)
f=lambda s,w,c=[]:[c]if''==s else[x for y in w for x in f(s[len(y):],w,c+[y])if s[:len(y)]==y]+f(s[1:],w,c+[s[0]])

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ 145 bytes \$\endgroup\$
    – Steffan
    Apr 9 at 18:36
  • \$\begingroup\$ @Steffan Thanks, updated \$\endgroup\$
    – Ajax1234
    Apr 9 at 18:37
  • \$\begingroup\$ 143 (sorry) \$\endgroup\$
    – Steffan
    Apr 9 at 18:39
1
\$\begingroup\$

Charcoal, 73 67 bytes

≔⟦⟦S⟧⟧θ≔⟦⟧ηWS⊞ηιFθ«≔⊟ιζ¿ζF⁺η⟦§ζ⁰⟧F⁼κ✂ζ⁰Lκ⊞θ⁺ι⟦κ✂ζLκ⟧⊞υι»⊟Φυ⁼Lι⌊EυLλ

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of words and outputs each substring on its own line (default output for an array of substrings). Explanation:

≔⟦⟦S⟧⟧θ

Start a breadth-first search with an empty substring list that still has the initial input to processes.

≔⟦⟧ηWS⊞ηι

Input the list of words.

Fθ«

Loop over the list of substring lists.

≔⊟ιζ

Remove the remainder of the input from this substring list.

¿ζ

If there is still any input left:

F⁺η⟦§ζ⁰⟧

For each of the input words, plus the first letter of the remainder of the input, ...

F⁼κ✂ζ⁰Lκ

... if the remainder of the input begins with this string, ...

⊞θ⁺ι⟦κ✂ζLκ⟧

... then push a new substring list obtained by splitting the input after that string.

⊞υι

Otherwise, save this substring list.

»⊟Φυ⁼Lι⌊EυLλ

Output any one shortest substring list.

\$\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.