Word Break Problem in DSA Rust - Build from Scratch

Word Break Problem

📖 Scenario: Imagine you have a long string of letters without spaces, and you want to check if it can be split into valid words from a dictionary. This is like trying to find spaces in a sentence that someone wrote without spaces.

🎯 Goal: You will build a program that checks if a given string can be broken into a sequence of dictionary words.

📋 What You'll Learn

Create a string variable with the exact value "applepenapple".

Create a vector of strings called word_dict with the exact entries "apple" and "pen".

Write a function called word_break that takes a string slice and a reference to a vector of strings and returns a boolean indicating if the string can be segmented into dictionary words.

Use dynamic programming inside word_break to solve the problem efficiently.

Print the result of calling word_break with the string and dictionary.

💡 Why This Matters

🌍 Real World

This problem is useful in text processing, like checking if a sentence without spaces can be split into valid words.

💼 Career

Understanding dynamic programming and string manipulation is important for software engineering roles involving algorithms and data processing.

1

Create the input string

Create a string variable called s with the exact value "applepenapple".

DSA Rust

# Create the input string variable 's'
# Your code here

Hint

Use let s = "applepenapple"; to create the string.

2

Create the dictionary vector

Create a vector of strings called word_dict with the exact entries "apple" and "pen".

DSA Rust

let s = "applepenapple";
# Create the vector 'word_dict' with entries "apple" and "pen"
# Your code here

Hint

Use vec!["apple".to_string(), "pen".to_string()] to create the vector.

3

Write the word_break function

Write a function called word_break that takes a string slice s and a reference to a vector of strings word_dict, and returns a boolean. Use dynamic programming with a boolean vector dp to check if s can be segmented into dictionary words.

DSA Rust

let s = "applepenapple";
let word_dict = vec!["apple".to_string(), "pen".to_string()];

// Write the function word_break below
// Your code here

Hint

Use a boolean vector dp of size n+1 where dp[i] means if s[0..i] can be segmented. Initialize dp[0] = true. Use nested loops to fill dp.

4

Print the result

Print the result of calling word_break(&s, &word_dict).

DSA Rust

let s = "applepenapple";
let word_dict = vec!["apple".to_string(), "pen".to_string()];

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

// Print the result of word_break
# Your code here

Hint

Use println!("{}", word_break(&s, &word_dict)); inside a main function to print the result.

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