LeetCode Blind 19/75: Word Break

Problem statement

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.
Link to problem

Example 1

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Solutions

Approach 1: Dynamic Programming

The gist of dynamic programming in this problem is trying to move a pointer forward in a.. decreasing fashion. The best way to explain this is through an example.

Imagine you are given "leetcode" and a word dict ["leet", "code"]

What you’re trying to do is this:

l

le 
 e

lee
 ee
  e

leet - match found

leetc
 eetc
  etc
   tc
    c

...

leetcode
 eetcode
  etcode
   tcode
    code - match found

Implementation in Rust

fn word_break(s: String, word_dict: Vec<String>) -> bool {
    let mut breakable = vec![false; s.len() + 1];
    breakable[0] = true;

    for end in 0..s.len() + 1 {
        for start in 0..end {
            let word = s[start..end].to_string();
            if breakable[start] && word_dict.contains(&word) {
                breakable[end] = true;
            }
        }
    }

    breakable[s.len()]
}

Time Complexity: $O(nm)$
$n$ is the length of string
$m$ is the length of word dict
Space Complexity: $O(n)$
Runtime on LeetCode: $3$ms

Other implemntations involve BFS/DFS which are simpler in concept but were quite difficulty for me to wrap my head around.