Word Break Problem in DSA Rust - Execution Trace

Concept Flow - Word Break Problem

Start with input string

↓

Check prefixes in dictionary

↓

Prefix found?

No→Try next prefix

Yes↓

Split string: prefix + suffix

↓

Recursively check suffix

↓

Suffix breakable?

No→Try next prefix

Yes↓

Return True

↓

End

The flow checks if the input string can be split into dictionary words by testing prefixes and recursively checking suffixes.

Execution Sample

DSA Rust

fn word_break(s: &str, dict: &Vec<&str>) -> bool {
    if s.is_empty() { return true; }
    for i in 1..=s.len() {
        let prefix = &s[0..i];
        if dict.contains(&prefix) && word_break(&s[i..], dict) {
            return true;
        }
    }
    false
}

This function checks if the string s can be segmented into words from dict by trying all prefixes.

Execution Table

Step	Operation	Current String	Prefix Checked	Prefix in Dict?	Recursive Call on Suffix	Result	Visual State
1	Check empty string	leetcode	-	-	-	No	leetcode
2	Check prefix	leetcode	l	No	-	-	leetcode
3	Check prefix	leetcode	le	No	-	-	leetcode
4	Check prefix	leetcode	lee	No	-	-	leetcode
5	Check prefix	leetcode	leet	Yes	word_break('code')	-	leetcode
6	Recursive call	code	-	-	-	No	code
7	Check prefix	code	c	No	-	-	code
8	Check prefix	code	co	No	-	-	code
9	Check prefix	code	cod	No	-	-	code
10	Check prefix	code	code	Yes	word_break('')	-	code
11	Recursive call		-	-	-	Yes
12	Return True	code	-	-	-	True	code
13	Return True	leetcode	-	-	-	True	leetcode

💡 All prefixes checked or successful segmentation found; final result returned.

Variable Tracker

Variable	Start	After Step 5	After Step 10	Final
s	leetcode	code		leetcode
prefix	-	leet	code	leetcode
Result	-	-	-	True

Key Moments - 3 Insights

Why do we check all prefixes instead of just one?

Because the string might be split in many ways, checking all prefixes ensures we find a valid segmentation if it exists, as shown in steps 2-5 and 7-10 in the execution_table.

What happens when the suffix is empty?

When suffix is empty (step 11), it means the entire string was successfully segmented, so we return True, ending recursion.

Why does the function return False sometimes?

If no prefix leads to a successful segmentation of the suffix, the function returns False, as seen in step 6 where 'code' initially returns No until full prefix 'code' is found.

Visual Quiz - 3 Questions

Look at the execution_table, what is the prefix checked at step 5?

A code

B leet

C lee

D l

💡 Hint

Check the 'Prefix Checked' column at step 5 in the execution_table.

At which step does the recursive call on an empty string return True?

A Step 11

B Step 6

C Step 13

D Step 1

💡 Hint

Look for the step where Current String is empty and Result is Yes.

If the dictionary did not contain 'leet', what would happen at step 5?

A Return True immediately

B Return False immediately

C Try next prefix

D Skip checking prefixes

💡 Hint

Refer to the 'Prefix in Dict?' and 'Operation' columns around step 5.

Concept Snapshot

Word Break Problem:
- Check if string can be split into dictionary words
- Try all prefixes; if prefix in dict, recursively check suffix
- Base case: empty string returns True
- Return True if any segmentation works, else False
- Uses recursion and dictionary lookup

Full Transcript

The Word Break Problem checks if a string can be split into valid words from a dictionary. The function tries all prefixes of the string. If a prefix is found in the dictionary, it recursively checks the remaining suffix. If the suffix is empty, it returns True, meaning the string can be segmented. If no prefix leads to a successful segmentation, it returns False. The execution table shows step-by-step prefix checks and recursive calls, tracking the current string and results. Key moments clarify why all prefixes are checked, what happens when suffix is empty, and why False is returned sometimes. The visual quiz tests understanding of prefix checks, recursion base case, and behavior when dictionary words are missing.

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