Word break

Array Hash Table String Dynamic Programming Trie Memoization

49.2% acceptance

Jan 12, 2026

18604

897

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. 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(s: String, word_dict: Vec<String>) -> bool {
    use std::collections::HashSet;
    
    let n = s.len();
    let words: HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
    let mut dp = vec![false; n + 1];
    dp[0] = true;
    
    for i in 1..=n {
      for j in 0..i {
        if dp[j] && words.contains(&s[j..i]) {
          dp[i] = true;
          break;
        }
      }
    }
    
    dp[n]
  }
}