Word Break Problem in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Break Check with Simple Dictionary

What is the output of this Rust code that checks if the string "applepenapple" can be segmented into dictionary words?

DSA Rust

fn word_break(s: &str, word_dict: &[&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] && word_dict.contains(&&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }
    dp[n]
}

fn main() {
    let s = "applepenapple";
    let word_dict = ["apple", "pen"];
    println!("{}", word_break(s, &word_dict));
}

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Think about whether the string can be split into words from the dictionary without leftover characters.

The string "applepenapple" can be segmented as "apple" + "pen" + "apple", all present in the dictionary. So the output is true.

❓ Predict Output

intermediate

Output of Word Break Check with No Possible Segmentation

What will this Rust code print when checking if "catsandog" can be segmented using the dictionary ["cats", "dog", "sand", "and", "cat"]?

DSA Rust

fn word_break(s: &str, word_dict: &[&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] && word_dict.contains(&&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }
    dp[n]
}

fn main() {
    let s = "catsandog";
    let word_dict = ["cats", "dog", "sand", "and", "cat"];
    println!("{}", word_break(s, &word_dict));
}

A Compilation error

B false

C true

D Runtime panic

💡 Hint

Check if the string can be split fully into dictionary words without leftover characters.

The string "catsandog" cannot be segmented fully because "og" is not in the dictionary. So the output is false.

🧠 Conceptual

advanced

Understanding Time Complexity of Word Break

What is the time complexity of the dynamic programming solution for the Word Break problem where n is the length of the string and m is the number of words in the dictionary?

A O(n^2 * m * k) where k is average word length

B O(n^3)

C O(n * m)

D O(n^2)

💡 Hint

Consider the nested loops and the substring checks against the dictionary.

The solution uses two nested loops over the string length (O(n^2)) and checks if substrings are in the dictionary (O(m * k) where k is average word length). So total is O(n^2 * m * k).

🔧 Debug

advanced

Identify the Bug in Word Break Implementation

What error will this Rust code produce when trying to run the word break function?

DSA Rust

fn word_break(s: &str, word_dict: &[&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] && word_dict.contains(&&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }
    dp[n]
}

fn main() {
    let s = "leetcode";
    let word_dict = ["leet", "code"];
    println!("{}", word_break(s, &word_dict));
}

A Compilation error due to missing semicolon

B Runs correctly and returns true

C Index out of bounds panic

D Returns false incorrectly

💡 Hint

Check the size of the dp vector and the indices accessed.

The dp vector is created with size n but accessed at dp[n], which is out of bounds causing a panic.

🚀 Application

expert

Number of Ways to Segment String Using Word Break

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

A 4

B 1

C 3

D 2

💡 Hint

Try to find all possible segmentations by splitting the string at different points.

The string can be segmented as "cats and dog" and "cat sand dog", so there are 2 ways.

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