Word break problem: Difference between revisions

=={{header|D}}==

{{trans|Java}}

<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;

}

}</lang>

{{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>