Word Break Problem in DSA Rust - Time & Space Complexity

Time Complexity: Word Break Problem

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to solve the Word Break Problem changes as the input grows.

Specifically, how does checking if a string can be split into dictionary words scale with string length?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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.contains(&s[j..i].to_string()) {
                dp[i] = true;
                break;
            }
        }
    }
    dp[n]
}
    

This code checks if the string s can be split into words from word_dict using dynamic programming.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops checking all substrings and dictionary membership.
• How many times: Outer loop runs n times; inner loop runs up to n times per outer loop; dictionary lookup inside inner loop.

How Execution Grows With Input

As the string length n grows, the number of substring checks grows roughly with the square of n.

Input Size (n)	Approx. Operations
10	About 100 substring checks
100	About 10,000 substring checks
1000	About 1,000,000 substring checks

Pattern observation: The operations grow roughly like the square of the input size.

Final Time Complexity

Time Complexity: O(n^3)

This means the time needed grows roughly with the cube of the string length because of substring creation and dictionary checks inside nested loops.

Common Mistake

[X] Wrong: "The solution runs in O(n^2) because there are only two loops."

[OK] Correct: Each substring check creates a new string and dictionary lookup can take up to O(m) time, adding an extra factor, where m is the length of the substring.

Interview Connect

Understanding this complexity helps you explain how dynamic programming solutions handle substring problems efficiently and what limits their speed.

Self-Check

"What if we used a hash set for the dictionary to speed up lookups? How would the time complexity change?"

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