In this challenge, your input is a string of lower-case letters like this:


and a dictionary like the that from my other challenge. You may assume that the dictionary file contains only lower-case letters and line-feed characters. Furthermore, the last character in the dictionary file is a line-feed character and the entries are sorted alphabetically.

Write a function that given these two strings, returns a single string containing all possible ways to insert spaces between some of the characters in the input string, such that the words created are all in the dictionary. Each possibility shall be terminated with a line-feed character. Some lines of the output for the example are:

insert spaces between words
insert space s between words
insert spaces between word s
insert space s between word s
insert spaces be tween words

The order of the output lines doesn't matter.

This is codegolf, the usual scoring rules apply, standard loopholes are verboten.

  • \$\begingroup\$ Are trailing spaces acceptable? \$\endgroup\$
    – Zgarb
    Feb 8, 2015 at 15:41
  • \$\begingroup\$ I still don't get the input format. Is it the string of letters and then each word in the dictionary? If so, how do we know when the input is done? \$\endgroup\$
    – KSFT
    Feb 8, 2015 at 15:42
  • \$\begingroup\$ @KSFT Your input is two strings. One string contains the dictionary, the other contains the word-string where you shall insert spaces. \$\endgroup\$
    – FUZxxl
    Feb 8, 2015 at 15:51
  • \$\begingroup\$ @Zgarb No. The question says “all possible ways to insert spaces between some of the characters in the input string;” trailing spaces are not between characters of the input string. \$\endgroup\$
    – FUZxxl
    Feb 8, 2015 at 15:54
  • \$\begingroup\$ Is the word s in your dictionary, but not other letters of the alphabet? \$\endgroup\$
    – feersum
    Feb 10, 2015 at 7:13

2 Answers 2


Python 3, 88

f=lambda x,w,s=[]:[x or print(*s)]+[x.find(y)or f(x[len(y):],w,s+[y])for y in w.split()]

String to split is x, the dictionary string is w.

The idea is to repeatedly check which strings y of the dictionary are a prefix for the current string x. The expression x.find(y) evaluates to the Falsey 0 only if x starts with y (substrings not present give -1), so the short-circuiting of or makes the function recurse down only when the prefixes matches. The prefix is chopped off with x[len(y):] and the list of subwords is updated in s.

When the whole string x has been consumed, we print the subwords s, automatically joined by spaces.


Haskell, 113 107 105 88 87 86 bytes

Works for empty inputs too (but gives an empty string as output).

s!d=unlines[w|w<-map concat$mapM(\c->[[c],[' ',c]])s,all(`elem`lines d).words$w,w>"!"]

Defines an infix binary function !. Call it like this:

"abababbaab" ! "ab\nba\na\nbab\n"


"ab ab ab ba ab\nab a bab ba ab\na bab ab ba ab\na ba bab ba ab\n"


The idea is to split the left input string s into words by inserting spaces in all possible ways, and keep those that consist of words of the dictionary d. A leading space is checked by comparing to the string "!".

s!d=                           -- Define the string s!d by
 unlines                       -- joining with line-breaks
  [w|w<-                       -- the strings w obtained by
    map concat$                -- concatenating each list of strings
    mapM(\c->[[c],[' ',c]])s,  -- obtained by replacing each letter 'c' of s by
                               -- either "c" or " c",
   all(`elem`lines d).         -- such that only lines of d
    words$w,                   -- occur as words in w, and
   w>"!"]                      -- w is lexicographically larger than "!",
                               -- which here means that w does not begin with a space.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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