7
\$\begingroup\$

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

insertspacesbetweenwords

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.

\$\endgroup\$
  • \$\begingroup\$ Are trailing spaces acceptable? \$\endgroup\$ – Zgarb Feb 8 '15 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 '15 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 '15 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 '15 at 15:54
  • \$\begingroup\$ Is the word s in your dictionary, but not other letters of the alphabet? \$\endgroup\$ – feersum Feb 10 '15 at 7:13
5
\$\begingroup\$

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"

Result:

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

Explanation

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.
\$\endgroup\$
8
\$\begingroup\$

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.

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