// 1061: Word Break — DP + HashSet
use std::collections::{HashMap, HashSet, VecDeque};
// Approach 1: Bottom-up DP
fn word_break(s: &str, words: &[&str]) -> bool {
let dict: HashSet<&str> = words.iter().copied().collect();
let n = s.len();
let mut dp = vec![false; n + 1];
dp[0] = true;
for i in 1..=n {
for j in 0..i {
if dp[j] && dict.contains(&s[j..i]) {
dp[i] = true;
break;
}
}
}
dp[n]
}
// Approach 2: Recursive with memoization
fn word_break_memo(s: &str, words: &[&str]) -> bool {
let dict: HashSet<&str> = words.iter().copied().collect();
fn solve<'a>(s: &'a str, start: usize, dict: &HashSet<&str>, cache: &mut HashMap<usize, bool>) -> bool {
if start == s.len() { return true; }
if let Some(&v) = cache.get(&start) { return v; }
let mut result = false;
for end_ in (start + 1)..=s.len() {
if dict.contains(&s[start..end_]) && solve(s, end_, dict, cache) {
result = true;
break;
}
}
cache.insert(start, result);
result
}
let mut cache = HashMap::new();
solve(s, 0, &dict, &mut cache)
}
// Approach 3: BFS approach
fn word_break_bfs(s: &str, words: &[&str]) -> bool {
let dict: HashSet<&str> = words.iter().copied().collect();
let n = s.len();
let mut visited = vec![false; n + 1];
let mut queue = VecDeque::new();
queue.push_back(0);
visited[0] = true;
while let Some(start) = queue.pop_front() {
for end_ in (start + 1)..=n {
if !visited[end_] && dict.contains(&s[start..end_]) {
if end_ == n { return true; }
visited[end_] = true;
queue.push_back(end_);
}
}
}
false
}
fn main() {
println!("word_break(\"leetcode\") = {}", word_break("leetcode", &["leet", "code"]));
println!("word_break(\"applepenapple\") = {}", word_break("applepenapple", &["apple", "pen"]));
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_word_break() {
assert!(word_break("leetcode", &["leet", "code"]));
assert!(word_break("applepenapple", &["apple", "pen"]));
assert!(!word_break("catsandog", &["cats", "dog", "sand", "and", "cat"]));
}
#[test]
fn test_word_break_memo() {
assert!(word_break_memo("leetcode", &["leet", "code"]));
assert!(!word_break_memo("catsandog", &["cats", "dog", "sand", "and", "cat"]));
}
#[test]
fn test_word_break_bfs() {
assert!(word_break_bfs("leetcode", &["leet", "code"]));
assert!(!word_break_bfs("catsandog", &["cats", "dog", "sand", "and", "cat"]));
}
}
(* 1061: Word Break — DP + HashSet *)
module StringSet = Set.Make(String)
(* Approach 1: Bottom-up DP *)
let word_break s words =
let dict = List.fold_left (fun acc w -> StringSet.add w acc) StringSet.empty words in
let n = String.length s in
let dp = Array.make (n + 1) false in
dp.(0) <- true;
for i = 1 to n do
for j = 0 to i - 1 do
if dp.(j) && StringSet.mem (String.sub s j (i - j)) dict then
dp.(i) <- true
done
done;
dp.(n)
(* Approach 2: Recursive with memoization *)
let word_break_memo s words =
let dict = List.fold_left (fun acc w -> StringSet.add w acc) StringSet.empty words in
let n = String.length s in
let cache = Hashtbl.create 32 in
let rec solve start =
if start = n then true
else
match Hashtbl.find_opt cache start with
| Some v -> v
| None ->
let v = ref false in
for end_ = start + 1 to n do
if not !v && StringSet.mem (String.sub s start (end_ - start)) dict then
v := solve end_
done;
Hashtbl.add cache start !v;
!v
in
solve 0
(* Approach 3: BFS approach *)
let word_break_bfs s words =
let dict = List.fold_left (fun acc w -> StringSet.add w acc) StringSet.empty words in
let n = String.length s in
let visited = Array.make (n + 1) false in
let queue = Queue.create () in
Queue.push 0 queue;
visited.(0) <- true;
while not (Queue.is_empty queue) do
let start = Queue.pop queue in
for end_ = start + 1 to n do
if not visited.(end_) && StringSet.mem (String.sub s start (end_ - start)) dict then begin
if end_ = n then (Queue.clear queue; visited.(n) <- true)
else begin
visited.(end_) <- true;
Queue.push end_ queue
end
end
done
done;
visited.(n)
let () =
assert (word_break "leetcode" ["leet"; "code"] = true);
assert (word_break "applepenapple" ["apple"; "pen"] = true);
assert (word_break "catsandog" ["cats"; "dog"; "sand"; "and"; "cat"] = false);
assert (word_break_memo "leetcode" ["leet"; "code"] = true);
assert (word_break_memo "catsandog" ["cats"; "dog"; "sand"; "and"; "cat"] = false);
assert (word_break_bfs "leetcode" ["leet"; "code"] = true);
assert (word_break_bfs "catsandog" ["cats"; "dog"; "sand"; "and"; "cat"] = false);
Printf.printf "✓ All tests passed\n"