Word Break Problem in DSA Rust

Mental Model

We want to check if a long word can be split into smaller valid words from a dictionary. We try breaking it step by step and remember what parts can form valid words.

Analogy: Imagine you have a long sentence without spaces, and you want to find where to put spaces so every word is in your dictionary. You try cutting the sentence at different points and check if the pieces are real words.

s: "leetcode"
Dictionary: ["leet", "code"]

Initial:
"leetcode"

Try splits:
"leet" | "code"

If both parts are in dictionary or can be split further, answer is yes.

Dry Run Walkthrough

Input: string: "leetcode", dictionary: ["leet", "code"]

Goal: Check if "leetcode" can be split into words from the dictionary

Step 1: Check prefix "l" - not in dictionary, move to next prefix

"l" (no), remaining "eetcode"

Why: Try smallest prefix to find valid word start

Step 2: Check prefix "le" - not in dictionary, move to next prefix

"le" (no), remaining "etcode"

Why: Continue checking longer prefixes

Step 3: Check prefix "lee" - not in dictionary, move to next prefix

"lee" (no), remaining "tcode"

Why: Still no valid prefix

Step 4: Check prefix "leet" - found in dictionary, now check suffix "code"

"leet" (yes), suffix "code" to check

Why: Found a valid prefix, now check if suffix can be split

Step 5: Check prefix "c" of suffix - not in dictionary, move to next prefix

"c" (no), remaining "ode"

Why: Try to split suffix

Step 6: Check prefix "co" - not in dictionary, move to next prefix

"co" (no), remaining "de"

Why: Continue checking suffix prefixes

Step 7: Check prefix "cod" - not in dictionary, move to next prefix

"cod" (no), remaining "e"

Why: Still no valid prefix

Step 8: Check prefix "code" - found in dictionary, suffix empty means success

"code" (yes), suffix empty

Why: Suffix fully matched dictionary words

Result:

"leet" -> "code" -> null (true)

Annotated Code

DSA Rust

use std::collections::HashSet;

struct Solution;

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let word_set: HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
        let n = s.len();
        let mut dp = vec![false; n + 1];
        dp[0] = true; // empty string can always be segmented

        for i in 1..=n {
            for j in 0..i {
                // Check if s[j..i] is in dictionary and dp[j] is true
                if dp[j] && word_set.contains(&s[j..i]) {
                    dp[i] = true;
                    break; // no need to check further splits for i
                }
            }
        }
        dp[n]
    }
}

fn main() {
    let s = "leetcode".to_string();
    let word_dict = vec!["leet".to_string(), "code".to_string()];
    let result = Solution::word_break(s, word_dict);
    println!("{}", result);
}

dp[0] = true; // empty string can always be segmented

Initialize base case: empty string is segmentable

for i in 1..=n {

Check all substring lengths from 1 to full string length

for j in 0..i {

Try all splits of substring s[0..i] into s[0..j] and s[j..i]

if dp[j] && word_set.contains(&s[j..i]) {

If prefix s[0..j] can be segmented and suffix s[j..i] is a word, mark dp[i]

dp[i] = true;

Mark substring s[0..i] as segmentable

break; // no need to check further splits for i

Stop checking splits once valid segmentation found

Output

true

Complexity Analysis

Time: O(n^2) because we check all substring splits for each position in the string

Space: O(n + m) where n is string length for dp array and m is dictionary size for hash set

vs Alternative: Naive recursion without memoization can be exponential; DP reduces repeated work to polynomial time

Edge Cases

Empty string s = ""

Returns true because empty string can be segmented trivially

DSA Rust

dp[0] = true; // empty string can always be segmented

String with no valid segmentation

Returns false because no combination of dictionary words can form s

DSA Rust

dp[i] remains false if no valid split found

Dictionary contains single character words

Algorithm still works by checking all splits

DSA Rust

if dp[j] && word_set.contains(&s[j..i]) {

When to Use This Pattern

When you need to check if a string can be split into dictionary words, use dynamic programming to remember which prefixes are valid to avoid repeated work.

Common Mistakes

Mistake: Not initializing dp[0] to true, causing no valid segmentation to start
Fix: Set dp[0] = true to represent empty string segmentation

Mistake: Checking substrings incorrectly with wrong indices
Fix: Use s[j..i] slices carefully ensuring j < i and within bounds

Mistake: Not breaking inner loop after finding a valid split, causing unnecessary checks
Fix: Add break after dp[i] = true to optimize

Summary

Checks if a string can be split into valid dictionary words using dynamic programming.

Use when you want to verify if a sentence without spaces can be segmented into known words.

Remember to build up solutions from smaller prefixes and store results to avoid repeated work.

Practice

1. What is the main goal of the Word Break Problem in algorithms?

easy

A. To reverse the characters of a string

B. To check if a string can be segmented into a sequence of dictionary words

C. To count the number of vowels in a string

D. To find the longest word in a dictionary

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks if a given string can be split into valid words from a dictionary.

2. Step 2: Identify the goal

   The goal is to verify if the entire string can be segmented into dictionary words without leftover characters.

3. Final Answer:

   To check if a string can be segmented into a sequence of dictionary words -> Option B

4. Quick Check:

   Word Break Problem = Check segmentation [OK]

Hint: Remember: Word Break checks if string splits into dictionary words [OK]

Common Mistakes:

• Confusing with finding longest word
• Thinking it counts characters
• Assuming it reverses strings

2. Which Rust data structure is best suited to store the dictionary words for the Word Break Problem?

easy

A. HashSet<String>

B. LinkedList<String>

C. Vec<String>

D. BinaryHeap<String>

Solution

1. Step 1: Consider dictionary lookup needs

   We need fast membership checking to see if a substring is in the dictionary.

2. Step 2: Choose data structure with fast lookup

   HashSet provides O(1) average time complexity for lookups, better than Vec or LinkedList.

3. Final Answer:

   HashSet<String> -> Option A

4. Quick Check:

   Fast lookup = HashSet [OK]

Hint: Use HashSet for quick word existence checks [OK]

Common Mistakes:

• Using Vec causes slow lookups
• LinkedList is inefficient for search
• BinaryHeap is for priority, not lookup

3. What will be the output of the following Rust code snippet for the input string "applepenapple" and dictionary ["apple", "pen"]?

fn word_break(s: &str, dict: &std::collections::HashSet<&str>) -> bool {
    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]
}

fn main() {
    let dict: std::collections::HashSet<&str> = ["apple", "pen"].iter().cloned().collect();
    println!("{}", word_break("applepenapple", &dict));
}

medium

A. Runtime panic

B. false

C. Compilation error

D. true

Solution

1. Step 1: Understand the dynamic programming logic

   The dp array tracks if substring s[0..i] can be segmented. dp[0] is true (empty string).

2. Step 2: Trace substring checks

   "apple" and "pen" are in dict, so "applepenapple" can be segmented as "apple" + "pen" + "apple".

3. Final Answer:

   true -> Option D

4. Quick Check:

   All substrings found = true [OK]

Hint: Check dp array for full string segmentation [OK]

Common Mistakes:

• Assuming false because of repeated words
• Confusing slice indices
• Expecting compilation error due to &str usage

4. Identify the bug in this Rust function for the Word Break Problem:

fn word_break(s: &str, dict: &std::collections::HashSet<&str>) -> bool {
    let n = s.len();
    let mut dp = vec![false; n];
    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]
}

medium

A. Missing return statement

B. Loop ranges are reversed

C. dp vector size is incorrect, should be n+1

D. dict.contains call uses wrong slice syntax

Solution

1. Step 1: Check dp vector initialization

   dp is initialized with size n, but dp[n] is accessed later, causing out-of-bounds error.

2. Step 2: Correct dp size

   dp should be size n+1 to hold dp[0] through dp[n] safely.

3. Final Answer:

   dp vector size is incorrect, should be n+1 -> Option C

4. Quick Check:

   dp size must cover full string length [OK]

Hint: dp size must be string length + 1 [OK]

Common Mistakes:

• Ignoring dp out-of-bounds panic
• Changing loop ranges unnecessarily
• Misunderstanding slice syntax

5. Given the string "catsanddog" and dictionary ["cat", "cats", "and", "sand", "dog"], how many different ways can the string be segmented into dictionary words?

hard

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: List possible segmentations

   Possible splits are "cats and dog" and "cat sand dog".

2. Step 2: Count valid segmentations

   There are exactly 2 ways to segment the string using the dictionary words.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Two valid segmentations found [OK]

Hint: Try all splits and count valid dictionary matches [OK]

Common Mistakes:

• Counting partial matches
• Missing one valid segmentation
• Assuming only one way always