Rosetta Code

Word break problem: Difference between revisions

Page Discussion

Word break problem (view source)

Revision as of 10:24, 17 February 2024

58,856 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
(Added Seed7 example)
m (→‎{{header|Wren}}: Minor tidy)
 
(34 intermediate revisions by 18 users not shown)
Line 1:
{{draft task}}
; Task:Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible.
 
 
{{Template:Strings}}
<br><br>
 
=={{header|11l}}==
{{trans|D}}
 
<syntaxhighlight lang="11l">T Node
String val
[String] parsed
F (val, [String] parsed = [String]())
.val = val
.parsed = copy(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’])</syntaxhighlight>
 
{{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>
 
=={{header|Aime}}==
<langsyntaxhighlight lang="aime">integer
wordbreak(record dict, text phrase, integer p, list words)
{
Line 58 ⟶ 133:
 
return 0;
}</langsyntaxhighlight>
{{Out}}
<pre>abcd: a b cd
Line 66 ⟶ 141:
abcdd: can't break</pre>
 
=={{header|ALGOL 68}}==
{{Trans|Nim}}
<syntaxhighlight lang="algol68"># utility functions: #
 
PROC includes = ([]STRING row, STRING s) BOOL:
# whether row includes s #
BEGIN
FOR i TO UPB row DO IF s = row[i] THEN true FI OD;
FALSE EXIT
true: TRUE
END;
 
PRIO & = 6;
OP & = (STRING s, []STRING row) []STRING:
# returns row with s prepended to it #
BEGIN
[UPB row + 1]STRING result;
result[2 : UPB result] := row;
result[1] := s;
result
END;
 
PROC add = (REF FLEX[]FLEX[]STRING rows, []STRING row) VOID:
# adds row to the end of rows (in place) #
BEGIN
[UPB rows+1]FLEX[0]STRING tmp;
tmp[:UPB rows] := rows;
tmp[UPB tmp] := row;
rows := tmp
END;
 
# actual solution: #
 
PROC word breaks = ([]STRING dict, STRING word) [][]STRING:
# build recursively the list of breaks for a word, using the given dictionary #
BEGIN
FLEX[0]FLEX[0]STRING result;
FOR last TO UPB word - 1 DO
STRING part1 := word[1 : last];
IF includes(dict, part1) THEN
STRING part2 := word[last + 1 : ];
IF includes(dict, part2) THEN add(result, (part1, part2)) FI;
[][]STRING sub results = word breaks(dict, part2);
FOR i FROM LWB sub results TO UPB sub results DO
add(result, part1 & sub results[i])
OD
FI
OD;
result
END;
 
PROC break word = ([]STRING dict, STRING word) VOID:
# find the ways to break a word and display the result #
BEGIN
print((word, ":", newline));
[][]STRING word seqs = word breaks(dict, word);
IF UPB word seqs = 0 THEN
print((" <no break possible>", newline))
ELSE
FOR i FROM LWB word seqs TO UPB word seqs DO
[]STRING seq = word seqs[i];
print(" ");
FOR j FROM LWB seq TO UPB seq DO
print((" ", seq[j]))
OD;
print(newline)
OD
FI
END;
 
[]STRING dict = ("a", "bc", "abc", "cd", "b");
 
[]STRING words = ("abcd", "abbc", "abcbcd", "acdbc", "abcdd");
 
FOR i TO UPB words DO
break word(dict, words[i])
OD</syntaxhighlight>
 
{{out}}
<pre>abcd:
a b cd
abbc:
a b bc
abcbcd:
a bc b cd
abc b cd
acdbc:
a cd bc
abcdd:
<no break possible>
</pre>
 
=={{header|C++}}==
{{trans|Rust}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <optional>
#include <set>
#include <string>
#include <string_view>
#include <vector>
 
struct string_comparator {
using is_transparent = void;
bool operator()(const std::string& lhs, const std::string& rhs) const {
return lhs < rhs;
}
bool operator()(const std::string& lhs, const std::string_view& rhs) const {
return lhs < rhs;
}
bool operator()(const std::string_view& lhs, const std::string& rhs) const {
return lhs < rhs;
}
};
 
using dictionary = std::set<std::string, string_comparator>;
 
template <typename iterator, typename separator>
std::string join(iterator begin, iterator end, separator sep) {
std::string result;
if (begin != end) {
result += *begin++;
for (; begin != end; ++begin) {
result += sep;
result += *begin;
}
}
return result;
}
 
auto create_string(const std::string_view& s,
const std::vector<std::optional<size_t>>& v) {
auto idx = s.size();
std::vector<std::string_view> sv;
while (v[idx].has_value()) {
size_t prev = v[idx].value();
sv.push_back(s.substr(prev, idx - prev));
idx = prev;
}
std::reverse(sv.begin(), sv.end());
return join(sv.begin(), sv.end(), ' ');
}
 
std::optional<std::string> word_break(const std::string_view& str,
const dictionary& dict) {
auto size = str.size() + 1;
std::vector<std::optional<size_t>> possible(size);
auto check_word = [&dict, &str](size_t i, size_t j)
-> std::optional<size_t> {
if (dict.find(str.substr(i, j - i)) != dict.end())
return i;
return std::nullopt;
};
for (size_t i = 1; i < size; ++i) {
if (!possible[i].has_value())
possible[i] = check_word(0, i);
if (possible[i].has_value()) {
for (size_t j = i + 1; j < size; ++j) {
if (!possible[j].has_value())
possible[j] = check_word(i, j);
}
if (possible[str.size()].has_value())
return create_string(str, possible);
}
}
return std::nullopt;
}
 
int main(int argc, char** argv) {
dictionary dict;
dict.insert("a");
dict.insert("bc");
dict.insert("abc");
dict.insert("cd");
dict.insert("b");
auto result = word_break("abcd", dict);
if (result.has_value())
std::cout << result.value() << '\n';
return 0;
}
</syntaxhighlight>
 
{{out}}
<pre>
a b cd
</pre>
 
=={{header|D}}==
{{trans|Java}}
<syntaxhighlight lang="d">import std.algorithm;
import std.range;
import std.stdio;
 
void main() {
string[] dict = ["a", "aa", "b", "ab", "aab"];
process(dict, ["aab", "aa b"]);
 
dict = ["abc", "a", "ac", "b", "c", "cb", "d"];
process(dict, ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"]);
}
 
void process(string[] dict, string[] testStrings) {
foreach (testString; testStrings) {
auto matches = wordBreak(testString, dict);
writeln("String = ", testString, ", Dictionary = ", dict, ". Solutions = ", matches.length);
foreach (match; matches) {
writeln(" Word Break = ", match);
}
writeln();
}
}
 
string[][] wordBreak(string s, string[] dictionary) {
string[][] matches;
Node[] queue = [Node(s)];
while (!queue.empty) {
auto node = queue.front;
queue.popFront;
// Check if fully parsed
if (node.val.length == 0) {
matches ~= node.parsed;
} else {
foreach (word; dictionary) {
// Check for match
if (node.val.startsWith(word)) {
auto valNew = node.val[word.length .. node.val.length];
auto parsedNew = node.parsed.dup;
parsedNew ~= word;
queue ~= Node(valNew, parsedNew);
}
}
}
}
return matches;
}
 
struct Node {
string val;
string[] parsed;
 
this(string initial) {
val = initial;
}
 
this(string s, string[] p) {
val = s;
parsed = p;
}
}</syntaxhighlight>
{{out}}
<pre>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>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| System.Generics.Collections}}
{{Trans|Go}}
<syntaxhighlight lang="delphi">
program Word_break_problem;
 
{$APPTYPE CONSOLE}
 
uses
System.SysUtils,
System.Generics.Collections;
 
type
TDict = TDictionary<string, boolean>;
 
TPrefix = record
length: integer;
broken: TArray<string>;
constructor Create(len: integer; b: TArray<string>);
end;
 
const
TESTS: TArray<string> = ['abcd', 'abbc', 'abcbcd', 'acdbc', 'abcdd'];
 
var
d: TDict;
 
function newDict(words: TArray<string>): TDict;
var
w: string;
begin
Result := TDict.Create();
for w in words do
Result.AddOrSetValue(w, true);
end;
 
function wordBreak(s: string; var broken: TArray<string>): boolean;
var
ed, i: Integer;
w: string;
p: TPrefix;
bp: TArray<TPrefix>;
begin
SetLength(broken, 0);
 
if s.IsEmpty then
exit(true);
 
bp := [TPrefix.Create(0, [])];
 
for ed := 1 to s.Length do
for i := High(bp) downto 0 do
begin
 
w := s.Substring(bp[i].length, ed - bp[i].length);
if d.ContainsKey(w) then
begin
broken := bp[i].broken + [w];
if ed = s.Length then
exit(true);
p := TPrefix.Create(ed, broken);
bp := bp + [p];
Break;
end;
end;
Result := false;
end;
 
{ TPrefix }
 
constructor TPrefix.Create(len: integer; b: TArray<string>);
begin
broken := b;
length := len;
end;
 
var
s: string;
b: TArray<string>;
ok: boolean;
 
begin
d := newDict(['a', 'bc', 'abc', 'cd', 'b']);
for s in TESTS do
if wordBreak(s, b) then
Writeln(Format('%s: %s', [s, string.join(' ', b)]))
else
Writeln('can''t break');
d.Free;
 
Readln;
end.</syntaxhighlight>
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 118 ⟶ 563:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>
Line 130 ⟶ 575:
=={{header|Haskell}}==
{{Trans|Javascript}}
<langsyntaxhighlight lang="haskell">import Data.TreeList (isPrefixOf, intercalate)
import Data.ListTree (isPrefixOf, intercalateTree(..))
 
wordBreaks :: [String] -> String -> String
wordBreaks ws s = (++) <*> (":\n" ++) . report . fmap go . tokenTrees ws
where
let parses = go <$> tokenTrees ws s
go t
| null (subForest t) = [rootLabel t]
| otherwise = subForest t >>= ((:) (rootLabel t) . go)
report xs
| null xs = "\tNot parseable with these words"
| otherwise = unlines $ (('\t' :) . intercalate " -> ") <$> xs
in s ++ (':' : '\n' : report parses)
 
tokenTrees :: [String] -> String -> [Tree String]
Line 157 ⟶ 601:
| otherwise = [Node w xs]
 
-------------------------- TEST ---------------------------
 
-- TEST ------------------------------------------------------------
ws, texts :: [String]
ws = words "a bc abc cd b"
Line 165 ⟶ 608:
 
main :: IO ()
main = (putStrLn . unlines) $ wordBreaks ws <$> texts</langsyntaxhighlight>
{{Out}}
<pre>abcd:
Line 182 ⟶ 625:
abcdd:
Not parseable with these words</pre>
 
=={{header|J}}==
With such short sentences we can find the partition sets, then check that all are words.
 
<syntaxhighlight lang="j">
all_partitions=: <@(<;.1)"1 _~ (1,.[:#:[:i.2^<:@:#) NB. all_partitions 'abcd'
word_break=: ([ #~ 0 = [: #&>@:] -.L:_1 _)~ all_partitions
main=: (] , (;:inv L:_1@:word_break >))"_ 0 boxopen
</syntaxhighlight>
 
<pre>
NB. demonstrate partitions of four integers
all_partitions i. 4
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│┌───────┐│┌─────┬─┐│┌───┬───┐│┌───┬─┬─┐│┌─┬─────┐│┌─┬───┬─┐│┌─┬─┬───┐│┌─┬─┬─┬─┐│
││0 1 2 3│││0 1 2│3│││0 1│2 3│││0 1│2│3│││0│1 2 3│││0│1 2│3│││0│1│2 3│││0│1│2│3││
│└───────┘│└─────┴─┘│└───┴───┘│└───┴─┴─┘│└─┴─────┘│└─┴───┴─┘│└─┴─┴───┘│└─┴─┴─┴─┘│
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
 
 
NB. demonstrate word_break
NB. (,L:_1]0;1 2;0 1 2;2 3;1)
NB. ┌─┬───┬─────┬───┬─┐
NB. │0│1 2│0 1 2│2 3│1│
NB. └─┴───┴─────┴───┴─┘
(,L:_1]0;1 2;0 1 2;2 3;1) word_break i. 4
┌─────────┐
│┌─┬─┬───┐│
││0│1│2 3││
│└─┴─┴───┘│
└─────────┘
 
 
NB. save and display the dictionary
[dictionary=: ;: 'a bc abc cd b'
┌─┬──┬───┬──┬─┐
│a│bc│abc│cd│b│
└─┴──┴───┴──┴─┘
 
NB. demonstrate main
dictionary main 'abc'
┌───┬───┬────┐
│abc│abc│a bc│
└───┴───┴────┘
 
NB. solution
dictionary main ;: 'abcd abbc abcbcd acdbc abcdd'
┌──────┬────────┬─────────┐
│abcd │a b cd │ │
├──────┼────────┼─────────┤
│abbc │a b bc │ │
├──────┼────────┼─────────┤
│abcbcd│abc b cd│a bc b cd│
├──────┼────────┼─────────┤
│acdbc │a cd bc │ │
├──────┼────────┼─────────┤
│abcdd │ │ │
└──────┴────────┴─────────┘
</pre>
 
=={{header|Java}}==
Accept string to be parsed, and dictionary of words, as method arguments.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
public class WordBreak {
 
public static void main(String[] args) {
List<String> dict = Arrays.asList("a", "aa", "b", "ab", "aab");
for ( String testString : Arrays.asList("aab", "aa b") ) {
List<List<String>> matches = wordBreak(testString, dict);
System.out.printf("String = %s, Dictionary = %s. Solutions = %d:%n", testString, dict, matches.size());
for ( List<String> match : matches ) {
System.out.printf(" Word Break = %s%n", match);
}
System.out.printf("%n");
}
dict = Arrays.asList("abc", "a", "ac", "b", "c", "cb", "d");
for ( String testString : Arrays.asList("abcd", "abbc", "abcbcd", "acdbc", "abcdd") ) {
List<List<String>> matches = wordBreak(testString, dict);
System.out.printf("String = %s, Dictionary = %s. Solutions = %d:%n", testString, dict, matches.size());
for ( List<String> match : matches ) {
System.out.printf(" Word Break = %s%n", match);
}
System.out.printf("%n");
}
}
private static List<List<String>> wordBreak(String s, List<String> dictionary) {
List<List<String>> matches = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(s));
while ( ! queue.isEmpty() ) {
Node node = queue.remove();
// Check if fully parsed
if ( node.val.length() == 0 ) {
matches.add(node.parsed);
}
else {
for ( String word : dictionary ) {
// Check for match
if ( node.val.startsWith(word) ) {
String valNew = node.val.substring(word.length(), node.val.length());
List<String> parsedNew = new ArrayList<>();
parsedNew.addAll(node.parsed);
parsedNew.add(word);
queue.add(new Node(valNew, parsedNew));
}
}
}
}
return matches;
}
private static class Node {
private String val; // Current unmatched string
private List<String> parsed; // Matches in dictionary
public Node(String initial) {
val = initial;
parsed = new ArrayList<>();
}
public Node(String s, List<String> p) {
val = s;
parsed = p;
}
}
 
}
</syntaxhighlight>
{{out}}
<pre>
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>
 
=={{header|Javascript}}==
Composing a solution from generic functions.
{{Trans|Python}}
<langsyntaxhighlight lang="javascript">(() => {
'use strict';
 
Line 297 ⟶ 903:
// MAIN ---
return main();
})();</langsyntaxhighlight>
{{Out}}
<pre>abcd:
Line 310 ⟶ 916:
abcdd:
(Not parseable with these words)</pre>
 
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
 
The solution offered here does not use regular expressions.
 
The function `string2words` is a generator that can produce all
possible parses of a string but which can be stopped after finding the
first parse, as in the first demonstration.
 
In the second demonstration, the generator is used to count the number
of possible parses using the same toy dictionary as used in the
first demonstration.
 
In the third demonstration, the well-known dictionary unixdict.txt is
used to determine the number of possible parses of the string "totalreturn".
 
<syntaxhighlight lang="jq">
def words: ["a", "bc", "abc", "cd", "b"];
def strings: ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"];
 
# input: an array of allowed words
# output: a stream giving all possible parses of the given string into
# the allowed words; each output is an array showing how the string
# has been parsed.
def string2words(string):
. as $dict
# Input: array of words
# Output: augmented array
| def s2w(s):
if s=="" then .
else $dict[] as $word
| (s|startswith($word)) as $ix
| if $ix
then s[$word|length:] as $rest
| (. + [$word]) | s2w($rest)
else empty
end
end;
[] | s2w(string);
 
def count(s): reduce s as $x (0; .+1) ;
def demo1:
strings[] as $s
| words
| (first(string2words($s)) // []) as $parsed
| "\($s) => \($parsed|join(" "))" ;
 
def demo2:
strings[] as $s
| words
| count(string2words($s))
| "\($s) has \(.) parse\(if . == 1 then "" else "s" end)." ;
 
# demo3 assumes an invocation along the lines of:
# jq -Rrn -f program.jq unixdict.txt
def demo3:
"returntotal" as $s
| "\($s) has \([inputs] | count(string2words($s)) parses."
demo1, " ", demo2, "", demo3
 
</syntaxhighlight>
{{out}}
<pre>
abcd => a b cd
abbc => a b bc
abcbcd => a bc b cd
acdbc => a cd bc
abcdd =>
 
abcd has 1 parse.
abbc has 1 parse.
abcbcd has 2 parses.
acdbc has 1 parse.
abcdd has 0 parses.
 
"returntotal" has 99 parses.
</pre>
 
 
=={{header|Julia}}==
Some extra loops to record and print all solutions.<langsyntaxhighlight Julialang="julia">
words = ["a", "bc", "abc", "cd", "b"]
strings = ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"]
Line 339 ⟶ 1,027:
end
 
wordbreak()</langsyntaxhighlight>
{{output}}<pre>
1 Solution(s) for abcd:
Line 354 ⟶ 1,042:
=={{header|Kotlin}}==
I've downloaded the free dictionary at http://www.puzzlers.org/pub/wordlists/unixdict.txt for this task. All single letters from 'a' to 'z' are considered to be words by this dictionary but 'bc' and 'cd' which I'd have expected to be present are not.
<langsyntaxhighlight lang="scala">// version 1.1.3
 
import java.io.File
Line 401 ⟶ 1,089:
println()
}
}</langsyntaxhighlight>
 
{{out}}
Line 425 ⟶ 1,113:
a b c d d
</pre>
 
=={{header|Lua}}==
<langsyntaxhighlight lang="lua">-- a specialized dict format is used to minimize the
-- possible candidates for this particalur problem
function genDict(ws)
Line 491 ⟶ 1,180:
for i=1,#test do
print(test[i],wordbreak(test[i]))
end</langsyntaxhighlight>
{{out}}
<pre>abcd a b cd
Line 498 ⟶ 1,187:
acdbc a cd bc
abcdd nil -no solution-</pre>
 
=={{header|Nim}}==
We provide two ways to initialize the dictionary: either explicitly by providing the list of words or by providing a file name from which extract the words. In the second case, it is possible to specify the minimal length of the words to keep. This is useful mainly to eliminate all the one letter words we get with “unixdict.txt”.
 
<syntaxhighlight lang="nim">import sequtils, sets, strutils
 
type
Dict = HashSet[string]
WordSeq = seq[string]
 
proc initDict(words: openArray[string]): Dict =
## Initialize a dictionary from a list of words.
words.toHashSet
 
proc initDict(fileName: string; minlength = 0): Dict =
## Initialize a dictionary with words from a file.
## Only words with minimal length are retained.
for word in filename.lines:
if word.len >= minLength:
result.incl word
 
func wordBreaks(dict: Dict; word: string): seq[WordSeq] =
## Build recursively the list of breaks for a word, using the given dictionary.
for last in 0..<word.high:
let part1 = word[0..last]
if part1 in dict:
let part2 = word[last+1..^1]
if part2 in dict: result.add(@[part1, part2])
result.add dict.wordBreaks(part2).mapIt(part1 & it)
 
proc breakWord(dict: Dict; word: string) =
## Find the ways to break a word and display the result.
echo word, ": "
let wordSeqs = dict.wordBreaks(word)
if wordSeqs.len == 0:
echo " <no break possible>"
else:
for wordSeq in wordSeqs:
echo " ", wordSeq.join(" ")
 
when isMainModule:
 
const EDict = ["a", "bc", "abc", "cd", "b"]
echo "Using explicit dictionary: ", EDict
var dict = initDict(EDict)
for s in ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"]:
dict.breakWord(s)
 
echo("\nUsing “unixdict.txt” dictionary without single letter words.")
dict = initDict("unixdict.txt", 2)
dict.breakWord("because")
dict.breakWord("software")</syntaxhighlight>
 
{{out}}
We used the same dictionary and words than in the other languages solutions and also added two examples using “unixdict.txt”.
<pre>Using explicit dictionary: ["a", "bc", "abc", "cd", "b"]
abcd:
a b cd
abbc:
a b bc
abcbcd:
a bc b cd
abc b cd
acdbc:
a cd bc
abcdd:
<no break possible>
 
Using “unixdict.txt” dictionary without single letter words.
because:
be cause
be ca use
software:
so ft ware
so ft wa re
soft ware
soft wa re</pre>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use strict;
use warnings;
 
Line 512 ⟶ 1,278:
@matches = $word =~ /^ ($one_of) ($one_of)? ($one_of)? ($one_of)? $/x; # sub-optimal: limited number of matches
return join(' ', grep {$_} @matches) || "(not possible)";
}</langsyntaxhighlight>
{{out}}
<pre>a: a
Line 526 ⟶ 1,292:
permissible: Not possible
mississippi: miss is sip pi</pre>
 
=={{header|Perl 6}}==
{{works with|Rakudo|2017.04}}
This implementation does not necessarily find ''every'' combination, it returns the one with the longest matching tokens.
 
<lang perl6>my @words = <a bc abc cd b>;
my $regex = @words.join('|');
 
put "$_: ", word-break($_) for <abcd abbc abcbcd acdbc abcdd>;
 
sub word-break (Str $word) { ($word ~~ / ^ (<$regex>)+ $ /)[0] // "Not possible" }</lang>
{{out}}
<pre>abcd: a b cd
abbc: a b bc
abcbcd: abc b cd
acdbc: a cd bc
abcdd: Not possible</pre>
 
=={{header|Phix}}==
The distributed version also contains a few experiments with applying a real dictionary, largely unsuccessful.
See talk page
<!--<syntaxhighlight lang="phix">(phixonline)-->
<lang Phix>procedure populate_dict(sequence s)
<span style="color: #000080;font-style:italic;">--
?s
-- demo\rosetta\Word_break_problem.exw
for i=1 to length(s) do setd(s[i],0) end for
-- ===================================
end procedure
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">populate_dict</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">populate_dict</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"a bc abc cd b"</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">prrec</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">sofar</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">show</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">sofar</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">prrec</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sofar</span><span style="color: #0000FF;">),</span><span style="color: #000000;">w</span><span style="color: #0000FF;">),</span><span style="color: #000000;">show</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">flattens</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- remove all nesting and empty sequences from a nested sequence of strings</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">si</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">flattens</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">wordend</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- (pretend a word just ended at start)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wordstarts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">wordends</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">wordend</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">pkey</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pkey</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pkey</span><span style="color: #0000FF;">)></span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span> <span style="color: #008080;">and</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">pkey</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pkey</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- exact match</span>
<span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">pkey</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">wordends</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">wordend</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wordends</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">worthwhile</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">worthwhile</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">worthwhile</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">wordend</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- (pretend a word just ended at start)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">wordend</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- eliminate any words that end before a wordstarts of {}.</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wl</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">wl</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">l</span> <span style="color: #008080;">and</span> <span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">wl</span><span style="color: #0000FF;">]={}</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wedx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">wl</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">wordends</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wedx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">worthwhile</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">else</span>
<span style="color: #000080;font-style:italic;">-- elimitate all words that start here.</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wl</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">wl</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">l</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wedx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">wl</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #000000;">wordends</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wedx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">worthwhile</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">wordend</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">wordends</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordends</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: not possible\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prrec</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,{},</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: 1 solution: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">flattens</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">))})</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">></span><span style="color: #000000;">20</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: %d solution(s): (too many to show)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">({</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wordends</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: %d solution(s):\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prrec</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wordstarts</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,{},</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"abcd"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"abbc"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"abcbcd"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"acdbc"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"abcdd"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
--/*
<!--</syntaxhighlight>-->
function valid_word(string word)
if length(word)=1 then return find(word,{"a","i"})!=0 end if
if find(word,{"sis","sst","se"}) then return false end if -- hack
for i=1 to length(word) do
integer ch = word[i]
if ch<'a'
or ch>'z' then
return false
end if
end for
return true
end function
--*/
 
populate_dict(split("a bc abc cd b"))
--/*
integer fn = open("demo\\unixdict.txt","r")
sequence words = get_text(fn,GT_LF_STRIPPED)
close(fn)
for i=length(words) to 1 by -1 do
if not valid_word(words[i]) then
words[i] = words[$]
words = words[1..$-1]
end if
end for
populate_dict(words)
--*/
 
function prrec(sequence wordstarts, integer idx, sequence sofar, bool show)
if idx>length(wordstarts) then
if show then
?sofar
end if
return 1
end if
integer res = 0
for i=1 to length(wordstarts[idx]) do
string w = wordstarts[idx][i]
res += prrec(wordstarts,idx+length(w),append(sofar,w),show)
end for
return res
end function
function flattens(sequence s)
-- remove all nesting and empty sequences from a nested sequence of strings
sequence res = {}, si
for i=1 to length(s) do
si = s[i]
if string(si) then
res = append(res,si)
else
res &= flattens(si)
end if
end for
return res
end function
procedure test(string s)
integer l = length(s)
sequence wordstarts = repeat({},l), wordends = repeat(0,l)
integer wordend = 1 -- (pretend a word just ended at start)
for i=1 to l do
if wordend then
for j=i to l do
object pkey = getd_partial_key(s[i..j])
if string(pkey) and length(pkey)>j-i and s[i..j]=pkey[1..j-i+1] then
if length(pkey)=j-i+1 then
-- exact match
wordstarts[i] = append(wordstarts[i],pkey)
wordends[j] += 1
end if
else
exit
end if
end for
end if
wordend = wordends[i]
end for
bool worthwhile = true
while worthwhile do
worthwhile = false
wordend = 1 -- (pretend a word just ended at start)
for i=1 to l do
if wordend then
-- eliminate any words that end before a wordstarts of {}.
for j=length(wordstarts[i]) to 1 by -1 do
integer wl = length(wordstarts[i][j])
if i+wl<=l and wordstarts[i+wl]={} then
wordends[i+wl-1] -= 1
wordstarts[i][j..j] = {}
worthwhile = true
end if
end for
else
-- elimitate all words that start here.
for j=1 to length(wordstarts[i]) do
integer wl = length(wordstarts[i][j])
if i+wl<=l then
wordends[i+wl-1] -= 1
worthwhile = true
end if
end for
wordstarts[i] = {}
end if
wordend = wordends[i]
end for
end while
--?{wordstarts,wordends}
if sum(wordends)=0 then
printf(1,"%s: not possible",{s})
else
integer count = prrec(wordstarts,1,{},false)
if count=1 then
printf(1,"%s: 1 solution: %s\n",{s,join(flattens(wordstarts))})
elsif count>20 then
printf(1,"%s: %d solution(s): (too many to show)\n",{s,count})
pp({wordstarts,wordends})
else
printf(1,"%s: %d solution(s):\n",{s,count})
count = prrec(wordstarts,1,{},true)
end if
end if
end procedure
constant tests = {"abcd","abbc","abcbcd","acdbc","abcdd"}
--constant tests = {"wordsisstringofspaceseparatedwords"}
for i=1 to length(tests) do test(tests[i]) end for</lang>
{{out}}
<pre>
Line 690 ⟶ 1,420:
abcdd: not possible
</pre>
 
=={{header|Picat}}==
===Non-determinism using member/2===
<code>s/2</code> checks all possible combinations. It uses <code>member/2</code> to select some element from Dict and backtracks if no solution is found.
<syntaxhighlight lang="picat">main =>
Tests = [["aab", ["a", "aa", "b", "ab", "aab"]],
["abba", ["a", "aa", "b", "ab", "aab"]],
["aa b", ["a", "aa", "b", "ab", "aab"]],
["abcd", ["abc", "a", "ac", "b", "c", "cb", "d"]],
["abbc", ["abc", "a", "ac", "b", "c", "cb", "d"]],
["abcbcd", ["abc", "a", "ac", "b", "c", "cb", "d"]],
["acdbc", ["abc", "a", "ac", "b", "c", "cb", "d"]],
["abcdd", ["abc", "a", "ac", "b", "c", "cb", "d"]]
],
foreach([String,Dict] in Tests)
println([string=String,dict=Dict]),
All = findall(S, S = s(Dict,String)),
println(All),
nl
end,
nl.
 
s(Dict,String) = S =>
S = [],
while(S.flatten != String, S.flatten.len < String.len)
member(D,Dict), % pick some element in Dict
S := S ++ [D]
end,
S.flatten==String.</syntaxhighlight>
 
{{out}}
<pre>[string = aab,dict = [a,aa,b,ab,aab]]
[[a,a,b],[a,ab],[aa,b],[aab]]
 
[string = abba,dict = [a,aa,b,ab,aab]]
[[a,b,b,a],[ab,b,a]]
 
[string = aa b,dict = [a,aa,b,ab,aab]]
[]
 
[string = abcd,dict = [abc,a,ac,b,c,cb,d]]
[[abc,d],[a,b,c,d]]
 
[string = abbc,dict = [abc,a,ac,b,c,cb,d]]
[[a,b,b,c]]
 
[string = abcbcd,dict = [abc,a,ac,b,c,cb,d]]
[[abc,b,c,d],[a,b,c,b,c,d],[a,b,cb,c,d]]
 
[string = acdbc,dict = [abc,a,ac,b,c,cb,d]]
[[a,c,d,b,c],[ac,d,b,c]]
 
[string = abcdd,dict = [abc,a,ac,b,c,cb,d]]
[[abc,d,d],[a,b,c,d,d]]</pre>
 
===Non-determinism using member/2 and append/3===
<code>s2/2</code> is more efficient. It uses <code>append/3</code> to extract the found prefix from the string.
<syntaxhighlight lang="picat">s2(Dict,String) = S =>
String2 = copy_term(String),
S = [],
while(S.flatten != String, S.flatten.len < String.len)
% Pick an element from Dict
member(D,Dict),
% Check that it fits and remove it from the string.
% If not: backtrack
append(D,String3,String2),
% ok!
String2 := String3,
S := S ++ [D]
end,
S.flatten==String.</syntaxhighlight>
 
===Using recursion===
<code>s3/2</code> use the same idea as <code>s2/2</code> but use recursion. Neater and more efficient.
<syntaxhighlight lang="picat">s3(Dict,String) = S =>
s3(Dict,String,S).
 
s3(_Dict,[],[]).
s3(Dict,String,[E|S]) :-
member(E,Dict),
append(E,String2,String),
s3(Dict,String2,S).</syntaxhighlight>
 
===Some tests===
Here is the test engine.
<syntaxhighlight lang="picat">main =>
garbage_collect(300_000_000),
_ = random2(),
Chars = "ab",
Dict = ["a", "aa", "b", "ab", "aab"],
println(dict=Dict),
String = [Chars[random(1,Chars.len)] : _ in 1..11],
% The tested strings
% String := "abbaabba",
% String := "babbbbaabbababb",
% String := "babbbbaabbababbaaaaababbaaabbb",
% String := "babbbbaabbababbaaaaababbaaabbbbaaabbbaba",
% String := "aabababbbaaabaababaaabababaaabbabbaabbba",
println(string=String),
All = findall(S, S = s3(Dict,String)),
Len = All.len,
if Len < 100 then
println(All)
end,
println(len=All.len),
nl.</syntaxhighlight>
 
As can be seen by this summary, <code>s3/2</code> is the most efficient of these versions. <code>s/2</code> is too slow but for the simplest examples.
{{out}}
<pre>dict = [a,aa,b,ab,aab]
string = abbaabba
[[a,b,b,a,a,b,b,a],[a,b,b,a,ab,b,a],[a,b,b,aa,b,b,a],[a,b,b,aab,b,a],[ab,b,a,a,b,b,a],[ab,b,a,ab,b,a],[ab,b,aa,b,b,a],[ab,b,aab,b,a]]
len = 8
 
s: 0.012s
s2: 0.0s
s3: 0.0
 
Dict = ["a", "aa", "b", "ab", "aab"],
string = babbbbaabbababb
[[b,a,b,b,b,b,a,a,b,b,a,b,a,b,b],[b,a,b,b,b,b,a,a,b,b,a,b,ab,b],[b,a,b,b,b,b,a,a,b,b,ab,a,b,b],[b,a,b,b,b,b,a,a,b,b,ab,ab,b],[b,a,b,b,b,b,a,ab,b,a,b,a,b,b],[b,a,b,b,b,b,a,ab,b,a,b,ab,b],[b,a,b,b,b,b,a,ab,b,ab,a,b,b],[b,a,b,b,b,b,a,ab,b,ab,ab,b],[b,a,b,b,b,b,aa,b,b,a,b,a,b,b],[b,a,b,b,b,b,aa,b,b,a,b,ab,b],[b,a,b,b,b,b,aa,b,b,ab,a,b,b],[b,a,b,b,b,b,aa,b,b,ab,ab,b],[b,a,b,b,b,b,aab,b,a,b,a,b,b],[b,a,b,b,b,b,aab,b,a,b,ab,b],[b,a,b,b,b,b,aab,b,ab,a,b,b],[b,a,b,b,b,b,aab,b,ab,ab,b],[b,ab,b,b,b,a,a,b,b,a,b,a,b,b],[b,ab,b,b,b,a,a,b,b,a,b,ab,b],[b,ab,b,b,b,a,a,b,b,ab,a,b,b],[b,ab,b,b,b,a,a,b,b,ab,ab,b],[b,ab,b,b,b,a,ab,b,a,b,a,b,b],[b,ab,b,b,b,a,ab,b,a,b,ab,b],[b,ab,b,b,b,a,ab,b,ab,a,b,b],[b,ab,b,b,b,a,ab,b,ab,ab,b],[b,ab,b,b,b,aa,b,b,a,b,a,b,b],[b,ab,b,b,b,aa,b,b,a,b,ab,b],[b,ab,b,b,b,aa,b,b,ab,a,b,b],[b,ab,b,b,b,aa,b,b,ab,ab,b],[b,ab,b,b,b,aab,b,a,b,a,b,b],[b,ab,b,b,b,aab,b,a,b,ab,b],[b,ab,b,b,b,aab,b,ab,a,b,b],[b,ab,b,b,b,aab,b,ab,ab,b]]
len = 32
s: 22.513s
s2: 0s
s3: 0s
 
Dict = ["a", "aa", "b", "ab", "aab"],
string = babbbbaabbababbaaaaababbaaabbb
len = 6144
s2: 0.088s
s3: 0.012s
 
Dict = [a,aa,b,ab,aab]
string = babbbbaabbababbaaaaababbaaabbbbaaabbbaba
len = 73728
s2: 1.466s
s3: 0.341
 
sdict = [a,aa,b,ab,aab]
string = aabababbbaaabaababaaabababaaabbabbaabbba
len = 884736
s2: 19.431 seconds
s3: 3.81 seconds</pre>
 
 
=={{header|PicoLisp}}==
<langsyntaxhighlight PicoLisplang="picolisp">(setq *Dict (quote "a" "bc" "abc" "cd" "b"))
(setq *Dict2
(quote
Line 732 ⟶ 1,608:
(println (word "samsungandmango" *Dict2))
(println (word "samsungandmangok" *Dict2))
(println (word "ksamsungandmango" *Dict2))</langsyntaxhighlight>
{{out}}
<pre>
Line 754 ⟶ 1,630:
 
{{Works with|Python|3.7}}
<langsyntaxhighlight lang="python">'''Parsing a string for word breaks'''
 
from itertools import (chain)
Line 856 ⟶ 1,732:
# MAIN ---
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{Out}}
<pre>abcd:
Line 873 ⟶ 1,749:
This returns all the possible splits (and null list if none is possible). Who's to say which is the best?
 
<langsyntaxhighlight lang="racket">#lang racket
 
(define render-phrases pretty-print)
Line 904 ⟶ 1,780:
(render-phrases (word-splits "samsungandmango" dict-2))
(render-phrases (word-splits "samsungandmangok" dict-2))
(render-phrases (word-splits "ksamsungandmango" dict-2)))</langsyntaxhighlight>
{{out}}
<pre>'("a b cd")
Line 920 ⟶ 1,796:
'()
'()</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2017.04}}
This implementation does not necessarily find ''every'' combination, it returns the one with the longest matching tokens.
 
<syntaxhighlight lang="raku" line>my @words = <a bc abc cd b>;
my $regex = @words.join('|');
 
put "$_: ", word-break($_) for <abcd abbc abcbcd acdbc abcdd>;
 
sub word-break (Str $word) { ($word ~~ / ^ (<$regex>)+ $ /)[0] // "Not possible" }</syntaxhighlight>
{{out}}
<pre>abcd: a b cd
abbc: a b bc
abcbcd: abc b cd
acdbc: a cd bc
abcdd: Not possible</pre>
 
=={{header|REXX}}==
This REXX version allows the words to be tested (and the dictionary words) to be specified on the command line.
<langsyntaxhighlight lang="rexx">/*REXX program breaks up a word (or string) into a list of words from a dictionary. */
parse arg a '/' x; a=space(a); x=space(x) /*get optional args; elide extra blanks*/
if a=='' | a=="," then a= 'abcd abbc abcbcd acdbc abcdd' /*maybeNot usespecififed? the defaults ?Use default*/
if x=='' | x=="," then x= 'a bc abc cd b' /* " " " " " */
na= words(a) /*the number of words to be tested. */
nx= words(x) /* " " " " " the dictionary*/
say nx ' dictionary words: ' x /*display the words in the dictionary. */
aw= 0 /*maximum word width obtained (so far).*/
say /*display a blank line to the terminal.*/
aw=0; do i=1 for na; _= word(a, i) /*obtain a word that will be tested. */
aw= max(aw, length(_) ) /*find widest width word being tested. */
end /*i*/ /* [↑] AW is used to align the output*/
@.=0 0 /*initialize the dictionary to "null". */
xw= 0
xw=0; do i=1 for nx; _=word(x, i) /*obtain a word from the dictionary. */
do xwi=max(xw,1 length(_) )for nx; @._=1 _= word(x, i) /*findobtain widesta widthword dictionaryfrom wordthe dictionary. */
xw= end /*i*/ max(xw, length(_) ); @._= 1 /*find [↑]widest define awidth dictionary word. */
p=0 end /*i*/ /* [↓↑] processdefine a dictionary word. in the A list.*/
p= 0 do j=1 for na; yy=word(a, j) /*YY: [↓] testprocess a word fromin the A list.*/
do tj=(nx+1)**(xw+1) byfor na; -1 to 1 until y==''; y=yy= word(a, j) /*tryYY: test a word possibility from the A list.*/
do $t=(nx+1)**(xw+1) by -1 to 1 until y==''; y= yy /*nullifytry theword (possible) result listpossibility. */
$= do try=t while y\='' /*keep testing until Y is exhausted /*nullify the (possible) result list. */
do ptry=(tryt + p)while y\='' // xw + 1 /*usekeep testing until a possibleY width foris thisexhausted. attempt*/
p=fw (y,try + p); if p==0// xw then iterate t /*is+ this1 part of the word not found ? /*use a possible width for this attempt*/
$p=$ ?fw(y, p); if p==0 then iterate t /*is this part of the word /*It wasnot found. Add partial to the? list*/
$= $ y=substr(y,? p + 1) /*now, use and test the rest of word /*It was found. Add partial to the list*/
y= substr(y, p + 1) end /*trynow, use and test the rest of word. */
end end /*ttry*/
end /*t*/
 
if t==0 then $= '(not possible)' /*indicate that the word isn't possible*/
say right(yy, aw) '───►' strip($) /*display the result to the terminal. */
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
fw: parse arg z,L; do k=L by -1 for L; ?=left(z,k); if @.? then leave; end; return k</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 968 ⟶ 1,864:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
# Project : Word break problem
 
Line 1,033 ⟶ 1,929:
next
next
</syntaxhighlight>
</lang>
Output:
<pre>
Line 1,040 ⟶ 1,936:
abcbcd = abc b cd
acdbc = a cd bc
</pre>
 
=={{header|Ruby}}==
 
<syntaxhighlight lang="ruby">
def split_text_with_dict(text, dict, splited=[])
solutions = []
dict.each do |word|
if text.start_with? word
new_text = text.delete_prefix word
new_splited = splited.dup<< word
if new_text.empty?
solutions << new_splited
else
sols = split_text_with_dict(new_text, dict, new_splited)
sols.each { |s| solutions << s }
end
end
end
return solutions
end
</syntaxhighlight>
 
{{out}}
<pre>
dict = ["a", "abc", "b", "bc", "cd"]
 
abcd => a b cd
abbc => a b bc
abcbcd
=> a bc b cd
=> abc b cd
acdbc => a cd bc
abcdd => No solution
 
</pre>
 
=={{header|Rust}}==
===Dynamic programming===
<langsyntaxhighlight lang="rust">use std::collections::HashSet;
fn create_string(s: &str, v: Vec<Option<usize>>) -> String {
let mut idx = s.len();
Line 1,089 ⟶ 2,020:
set.insert("b");
println!("{:?}", word_break("abcd", set).unwrap());
}</langsyntaxhighlight>
{{output}}
<pre>"a b cd"</pre>
Line 1,096 ⟶ 2,027:
===First solution===
Finds all possible solutions recursively, using a trie representation of the dictionary:
<langsyntaxhighlight lang="scala">case class TrieNode(isWord: Boolean, children: Map[Char, TrieNode]) {
def add(s: String): TrieNode = s match {
case "" => copy(isWord = true)
Line 1,129 ⟶ 2,060:
def wordBreak(s: String, dict: TrieNode): List[List[String]] = {
wordBreakRec(s, dict, dict, "")
}</langsyntaxhighlight>
Calling it with some example strings:
<langsyntaxhighlight lang="scala">val dict = buildTrie("a", "bc", "abc", "cd", "b")
val testCases = List("abcd", "abbc", "abcbcd", "acdbc", "abcdd")
for (s <- testCases) {
Line 1,139 ⟶ 2,070:
println("\t" + words.mkString(" "))
}
}</langsyntaxhighlight>
{{out}}
<pre>abcd has 1 solution(s):
Line 1,153 ⟶ 2,084:
===Combined solution===
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/49YwsD5/1 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/L47OzgmjSkOnQ5wfrZ5snQ Scastie (remote JVM)].
<langsyntaxhighlight Scalalang="scala">object WordBreak extends App {
val dict = buildTrie("a", "bc", "abc", "cd", "b")
lazy val empty = TrieNode(isWord = false, Map.empty) // lazy or in a companion object
Line 1,202 ⟶ 2,133:
})
 
}</langsyntaxhighlight>
 
=={{header|Seed7}}==
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
 
const func boolean: wordBreak (in string: stri, in array string: words, in string: resultList) is func
Line 1,238 ⟶ 2,169:
end if;
end for;
end func;</langsyntaxhighlight>
 
{{out}}
Line 1,252 ⟶ 2,183:
=={{header|Sidef}}==
{{trans|zkl}}
<langsyntaxhighlight lang="ruby">func word_break (str, words) {
 
var r = ->(str, arr=[]) {
Line 1,274 ⟶ 2,205:
for str in (strs) {
printf("%11s: %s\n", str, word_break(str, words) \\ '(not possible)')
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,285 ⟶ 2,216:
permission: ["per", "miss", "ion"]
mississippi: ["miss", "is", "sip", "pi"]
</pre>
 
=={{header|Swift}}==
 
{{trans|Rust}}
 
<syntaxhighlight lang="swift">infix operator ??= : AssignmentPrecedence
 
@inlinable
public func ??= <T>(lhs: inout T?, rhs: T?) {
lhs = lhs ?? rhs
}
 
private func createString(_ from: String, _ v: [Int?]) -> String {
var idx = from.count
var sliceVec = [Substring]()
 
while let prev = v[idx] {
let s = from.index(from.startIndex, offsetBy: prev)
let e = from.index(from.startIndex, offsetBy: idx)
sliceVec.append(from[s..<e])
idx = prev
}
 
return sliceVec.reversed().joined(separator: " ")
}
 
public func wordBreak(str: String, dict: Set<String>) -> String? {
let size = str.count + 1
var possible = [Int?](repeating: nil, count: size)
 
func checkWord(i: Int, j: Int) -> Int? {
let s = str.index(str.startIndex, offsetBy: i)
let e = str.index(str.startIndex, offsetBy: j)
 
return dict.contains(String(str[s..<e])) ? i : nil
}
 
for i in 1..<size {
possible[i] ??= checkWord(i: 0, j: i)
 
guard possible[i] != nil else {
continue
}
 
for j in i+1..<size {
possible[j] ??= checkWord(i: i, j: j)
}
 
if possible[str.count] != nil {
return createString(str, possible)
}
}
 
return nil
}
 
let words = [
"a",
"bc",
"abc",
"cd",
"b"
] as Set
 
let testCases = [
"abcd",
"abbc",
"abcbcd",
"acdbc",
"abcdd"
]
 
for test in testCases {
print("\(test):")
print(" \(wordBreak(str: test, dict: words) ?? "did not parse with given words")")
}</syntaxhighlight>
 
{{out}}
 
<pre>abcd:
a b cd
abbc:
a b bc
abcbcd:
a bc b cd
acdbc:
a cd bc
abcdd:
did not parse with given words</pre>
 
=={{header|Tailspin}}==
Does a depth-first search (after generating all possibilities on the current level). We could stop looking further after one is found, just add a condition to do nothing if a done-flag is set.
<syntaxhighlight lang="tailspin">
templates wordBreaks&{dict:}
composer starts&{with:}
<does|not>
rule does: (<=$with>) <'.*'>
rule not: <'.*'> -> \(!VOID\)
end starts
'Breaking "$;" by $dict;:$#10;' -> !OUT::write
{ words:[], remaining: $} -> #
'--done--$#10;' !
 
when <{remaining: <=''>}> do
$.words -> \spaceSeparate[i](when <?($i <=1>)> do $! otherwise ' ' ! $ ! \spaceSeparate) -> '$...;$#10;' !
otherwise
def base: $;
$dict... -> \(
def word: $;
$base.remaining -> starts&{with: $word} -> {words: [$base.words..., $word], remaining: $} !
\) -> #
end wordBreaks
 
'ababab' -> wordBreaks&{dict: ['a', 'ab', 'bab']} -> !OUT::write
'abcbab' -> wordBreaks&{dict: ['a', 'ab', 'bab']} -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Breaking "ababab" by [a, ab, bab]:
a bab ab
ab a bab
ab ab ab
--done--
Breaking "abcbab" by [a, ab, bab]:
--done--
</pre>
 
=={{header|Visual Basic .NET}}==
{{trans|Java}}
<syntaxhighlight lang="vbnet">Module Module1
 
Structure Node
Private ReadOnly m_val As String
Private ReadOnly m_parsed As List(Of String)
 
Sub New(initial As String)
m_val = initial
m_parsed = New List(Of String)
End Sub
 
Sub New(s As String, p As List(Of String))
m_val = s
m_parsed = p
End Sub
 
Public Function Value() As String
Return m_val
End Function
 
Public Function Parsed() As List(Of String)
Return m_parsed
End Function
End Structure
 
Function WordBreak(s As String, dictionary As List(Of String)) As List(Of List(Of String))
Dim matches As New List(Of List(Of String))
Dim q As New Queue(Of Node)
q.Enqueue(New Node(s))
While q.Count > 0
Dim node = q.Dequeue()
REM check if fully parsed
If node.Value.Length = 0 Then
matches.Add(node.Parsed)
Else
For Each word In dictionary
REM check for match
If node.Value.StartsWith(word) Then
Dim valNew = node.Value.Substring(word.Length, node.Value.Length - word.Length)
Dim parsedNew As New List(Of String)
parsedNew.AddRange(node.Parsed)
parsedNew.Add(word)
q.Enqueue(New Node(valNew, parsedNew))
End If
Next
End If
End While
Return matches
End Function
 
Sub Main()
Dim dict As New List(Of String) From {"a", "aa", "b", "ab", "aab"}
For Each testString In {"aab", "aa b"}
Dim matches = WordBreak(testString, dict)
Console.WriteLine("String = {0}, Dictionary = {1}. Solutions = {2}", testString, dict, matches.Count)
For Each match In matches
Console.WriteLine(" Word Break = [{0}]", String.Join(", ", match))
Next
Console.WriteLine()
Next
 
dict = New List(Of String) From {"abc", "a", "ac", "b", "c", "cb", "d"}
For Each testString In {"abcd", "abbc", "abcbcd", "acdbc", "abcdd"}
Dim matches = WordBreak(testString, dict)
Console.WriteLine("String = {0}, Dictionary = {1}. Solutions = {2}", testString, dict, matches.Count)
For Each match In matches
Console.WriteLine(" Word Break = [{0}]", String.Join(", ", match))
Next
Console.WriteLine()
Next
End Sub
 
End Module</syntaxhighlight>
{{out}}
<pre>String = aab, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 4
Word Break = [aab]
Word Break = [a, ab]
Word Break = [aa, b]
Word Break = [a, a, b]
 
String = aa b, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 0
 
String = abcd, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 2
Word Break = [abc, d]
Word Break = [a, b, c, d]
 
String = abbc, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 1
Word Break = [a, b, b, c]
 
String = abcbcd, Dictionary = System.Collections.Generic.List`1[System.String]. 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 = System.Collections.Generic.List`1[System.String]. Solutions = 2
Word Break = [ac, d, b, c]
Word Break = [a, c, d, b, c]
 
String = abcdd, Dictionary = System.Collections.Generic.List`1[System.String]. Solutions = 2
Word Break = [abc, d, d]
Word Break = [a, b, c, d, d]</pre>
 
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
 
class Prefix {
construct new(length, broken) {
_length = length
_broken = broken
}
length { _length }
broken { _broken }
}
 
var wordBreak = Fn.new { |d, s|
if (s == "") return [[], true]
var bp = [Prefix.new(0, [])]
for (end in 1..s.count) {
for (i in bp.count-1..0) {
var w = s[bp[i].length...end]
if (d[w]) {
var b = bp[i].broken.toList
b.add(w)
if (end == s.count) return [b, true]
bp.add(Prefix.new(end, b))
break
}
}
}
return [[], false]
}
 
var words = ["a", "bc", "abc", "cd", "b"]
var d = {}
words.each { |w| d[w] = true }
for (s in ["abcd", "abbc", "abcbcd", "acdbc", "abcdd"]) {
var res = wordBreak.call(d, s)
if (res[1]) {
Fmt.print("$s: $s", s, res[0].join(" "))
} else {
System.print("can't break")
}
}</syntaxhighlight>
 
{{out}}
<pre>
abcd: a b cd
abbc: a b bc
abcbcd: a bc b cd
acdbc: a cd bc
can't break
</pre>
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn wordBreak(str,words){ // words is string of space seperated words
words=words.split(" "); // to list of words
r:=fcn(str,words,sink){ // recursive search, easy to collect answer
Line 1,302 ⟶ 2,519:
if(False==r) return("not possible");
r.reverse().concat(" ")
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">foreach text in (T("abcd","abbc","abcbcd","acdbc","abcdd")){
println(text,": ",wordBreak(text,"a bc abc cd b"))
}</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/275372...353260"