Word break ii

Array Hash Table String Dynamic Programming Backtracking Trie Memoization

55.1% acceptance

Jan 12, 2026

7539

549

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn word_break_ii(s: String, word_dict: Vec<String>) -> Vec<String> {
    use std::collections::{HashMap, HashSet};
    
    let words: HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
    let mut memo: HashMap<usize, Vec<String>> = HashMap::new();
    
    fn backtrack<'a>(
      s: &'a str,
      start: usize,
      words: &HashSet<&'a str>,
      memo: &mut HashMap<usize, Vec<String>>,
    ) -> Vec<String> {
      if let Some(cached) = memo.get(&start) {
        return cached.clone();
      }
      
      if start == s.len() {
        return vec![String::new()];
      }
      
      let mut result = Vec::new();
      for end in start + 1..=s.len() {
        let word = &s[start..end];
        if words.contains(word) {
          let sub_results = backtrack(s, end, words, memo);
          for sub in sub_results {
            if sub.is_empty() {
              result.push(word.to_string());
            } else {
              result.push(format!("{} {}", word, sub));
            }
          }
        }
      }
      
      memo.insert(start, result.clone());
      result
    }
    
    backtrack(&s, 0, &words, &mut memo)
  }
}