Word break problem: Difference between revisions
Content deleted Content added
Alextretyak (talk | contribs) Added 11l |
|||
Line 1,013:
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”.
<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")</lang>
{{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}}==
|