Word Break Problem in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the input string is empty.

DSA Rust

if s.[1]() { return true; }

Drag options to blanks, or click blank then click option'

Astarts_with

Bis_empty

Ccontains

Dlen

Attempts:

3 left

💡 Hint

Common Mistakes

Using len() without comparing to zero

Using contains() which checks for substring presence

Using starts_with() which checks the beginning of the string

The is_empty() method checks if the string has zero length, which means it's empty.

2fill in blank

medium

Complete the code to iterate over the dictionary words.

DSA Rust

for word in word_dict.[1]() { /* check prefix */ }

Drag options to blanks, or click blank then click option'

Aiter

Bkeys

Cvalues

Dinto_iter

Attempts:

3 left

💡 Hint

Common Mistakes

Using keys() which is for maps, not vectors

Using values() which is for maps, not vectors

Using into_iter() which consumes the vector

The iter() method returns an iterator over references to the elements, suitable for checking each word.

3fill in blank

hard

Fix the error in the prefix check condition.

DSA Rust

if s.starts_with([1]) { /* proceed */ }

Drag options to blanks, or click blank then click option'

A*word

Bword

Cword.as_str()

D&word

Attempts:

3 left

💡 Hint

Common Mistakes

Passing &word directly which is &String, not &str

Using *word which is invalid syntax

Passing word without reference

The starts_with method expects a string slice (&str), so we convert the String to &str using as_str().

4fill in blank

hard

Fill both blanks to slice the string and recursively check the rest.

DSA Rust

let suffix = &s[[1]..];
if word_break(suffix, word_dict) == [2] { return true; }

Drag options to blanks, or click blank then click option'

Aword.len()

Btrue

Cfalse

Ds.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Using s.len() which slices the whole string

Checking for false instead of true

Using incorrect slice indices

We slice the string from the length of the matched word to the end, then recursively check if the suffix can be segmented. If it returns true, we return true.

5fill in blank

hard

Fill all three blanks to complete the word break function with memoization.

DSA Rust

fn word_break_memo(s: &str, word_dict: &Vec<String>, memo: &mut std::collections::HashMap<String, bool>) -> bool {
    if s.is_empty() { return true; }
    if let Some(&result) = memo.get(&s.to_string()) {
        return [1];
    }
    for word in word_dict.iter() {
        if s.starts_with(word.as_str()) {
            let suffix = &s[[2]..];
            if word_break_memo(suffix, word_dict, memo) == [3] {
                memo.insert(s.to_string(), true);
                return true;
            }
        }
    }
    memo.insert(s.to_string(), false);
    false
}

Drag options to blanks, or click blank then click option'

Aresult

Bword.len()

Ctrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Returning s instead of result from memo

Using incorrect slice indices

Checking for false instead of true in recursion

We return the cached result if present. The suffix is sliced from the length of the matched word. If the recursive call returns true, we cache and return true.

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