Word break problem: Difference between revisions

=={{header|11l}}==

{{trans|D}}

<lang 11l>T Node

String val

[String] parsed

F (val, [String] &parsed = [String]())

.val = val

.parsed = parsed

F word_break(s, dictionary)

[[String]] matches

V queue = Deque([Node(s)])

L !queue.empty

V node = queue.pop_left()

I node.val.empty

matches [+]= node.parsed

E

L(word) dictionary

I node.val.starts_with(word)

V val_new = node.val[word.len .< node.val.len]

V parsed_new = copy(node.parsed)

parsed_new [+]= word

queue [+]= Node(val_new, &parsed_new)

R matches

F process(d, test_strings)

L(test_string) test_strings

V matches = word_break(test_string, d)

print((‘String = ’test_string‘, Dictionary = ’String(d)‘. Solutions =’)‘ ’matches.len)

L(match) matches

print(‘ Word Break = ’match)

print()

V d = [‘a’, ‘aa’, ‘b’, ‘ab’, ‘aab’]

process(d, [‘aab’, ‘aa b’])

d = [‘abc’, ‘a’, ‘ac’, ‘b’, ‘c’, ‘cb’, ‘d’]

process(d, [‘abcd’, ‘abbc’, ‘abcbcd’, ‘acdbc’, ‘abcdd’])</lang>

{{out}}

<pre style="height:45ex;overflow:scroll">

String = aab, Dictionary = [a, aa, b, ab, aab]. Solutions = 4

Word Break = [aab]

Word Break = [a, ab]

Word Break = [aa, b]

Word Break = [a, a, b]

String = aa b, Dictionary = [a, aa, b, ab, aab]. Solutions = 0

String = abcd, Dictionary = [abc, a, ac, b, c, cb, d]. Solutions = 2

Word Break = [abc, d]

Word Break = [a, b, c, d]

String = abbc, Dictionary = [abc, a, ac, b, c, cb, d]. Solutions = 1

Word Break = [a, b, b, c]

String = abcbcd, Dictionary = [abc, a, ac, b, c, cb, d]. Solutions = 3

Word Break = [abc, b, c, d]

Word Break = [a, b, cb, c, d]

Word Break = [a, b, c, b, c, d]

String = acdbc, Dictionary = [abc, a, ac, b, c, cb, d]. Solutions = 2

Word Break = [ac, d, b, c]

Word Break = [a, c, d, b, c]

String = abcdd, Dictionary = [abc, a, ac, b, c, cb, d]. Solutions = 2

Word Break = [abc, d, d]

Word Break = [a, b, c, d, d]

</pre>