Word Break Problem in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Word Break Problem?

It is a problem where you check if a given string can be split into a sequence of dictionary words.

beginner

What data structure is commonly used to solve the Word Break Problem efficiently?

A dynamic programming table (usually a boolean array) is used to store if substrings can be segmented.

intermediate

In the Word Break Problem, what does dp[i] represent in a dynamic programming solution?

dp[i] is true if the substring from the start to index i-1 can be segmented into dictionary words.

intermediate

Why do we check all substrings ending at position i in the Word Break Problem?

To find if any prefix substring can be segmented and the remaining substring is a dictionary word, making dp[i] true.

advanced

What is the time complexity of the dynamic programming solution to the Word Break Problem?

It is O(n^3) in the worst case because for each position, we check all substrings and dictionary lookups.

What does the Word Break Problem ask you to determine?

A If a string has repeated characters

B If a string is a palindrome

C If a string can be segmented into dictionary words

D If a string contains only vowels

The Word Break Problem checks if the string can be split into valid dictionary words.

In the dynamic programming solution, what is the initial value of dp[0]?

A False

B True

C Depends on the string

D Undefined

dp[0] is true because an empty string can be segmented trivially.

Which of these is NOT a step in the Word Break dynamic programming approach?

A Sort the dictionary words

B Use a boolean array to store results

C Check all substrings ending at current index

D Check if substring is in dictionary

Sorting dictionary words is not required for the DP solution.

If dp[i] is true, what does it mean?

A Substring s[0..i-1] can be segmented into dictionary words

B Substring s[i..end] is a dictionary word

C The entire string is a dictionary word

D No segmentation possible

dp[i] true means substring from start to i-1 can be segmented.

What is the main challenge in the Word Break Problem?

A Counting vowels

B Finding the longest dictionary word

C Sorting the input string

D Checking all possible segmentations efficiently

The challenge is to check all segmentations efficiently using DP.

Explain how dynamic programming helps solve the Word Break Problem.

Think about how you remember which parts of the string can be segmented.

Describe the steps to implement the Word Break Problem solution in Rust.

Focus on loops, substring checks, and dp updates.

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