Word break problem
Word break problem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Task
- Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible.
Perl 6
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) {
my $words = $word ~~ / ^ (<$regex>)+ $ /; $words[0] // "Not possible";
}</lang>
- Output:
abcd: a b cd abbc: a b bc abcbcd: abc b cd acdbc: a cd bc abcdd: Not possible
Rust
Dynamic programming
<lang rust>use std::collections::HashSet; fn create_string(s: &str, v: Vec<Option<usize>>) -> String {
let mut idx = s.len(); let mut slice_vec = vec![]; while let Some(prev) = v[idx] { slice_vec.push(&s[prev..idx]); idx = prev; } slice_vec.reverse(); slice_vec.join(" ")
}
fn word_break(s: &str, dict: HashSet<&str>) -> Option<String> {
let size = s.len() + 1; let mut possible = vec![None; size];
let check_word = |i,j| dict.get(&s[i..j]).map(|_| i);
for i in 1..size { possible[i] = possible[i].or_else(|| check_word(0,i));
if possible[i].is_some() { for j in i+1..size { possible[j] = possible[j].or_else(|| check_word(i,j)); }
if possible[s.len()].is_some() { return Some(create_string(s, possible)); }
}; } None
}
fn main() {
let mut set = HashSet::new(); set.insert("a"); set.insert("bc"); set.insert("abc"); set.insert("cd"); set.insert("b"); println!("{:?}", word_break("abcd", set).unwrap());
}</lang>
- Output:
"a b cd"