Word Break Problem in DSA C++ - Deep Dive

Overview - Word Break Problem

What is it?

The Word Break Problem asks if a given string can be split into a sequence of valid words from a dictionary. You check if the string can be broken down so that every piece is a word you know. This helps in understanding how to break problems into smaller parts and use memory to avoid repeating work.

Why it matters

Without this concept, computers would struggle to quickly check if sentences or strings are meaningful combinations of words. It solves the problem of efficiently parsing text, which is important in spell checkers, text messaging apps, and language processing. Without it, these applications would be slow or inaccurate.

Where it fits

Before learning this, you should understand basic strings and arrays. After this, you can explore dynamic programming deeply and move on to more complex string problems like pattern matching or segmentation.

Mental Model

Core Idea

The Word Break Problem is about checking if a string can be built by joining smaller known words without leftover parts.

Think of it like...

Imagine you have a long necklace made of beads, and you want to see if you can split it into smaller necklaces using only beads from your favorite bead sets. If you can, the necklace is valid.

Input String: s = "applepenapple"
Dictionary: {"apple", "pen"}

Check positions:
[0] -> "apple" is in dictionary -> check rest
[5] -> "pen" is in dictionary -> check rest
[8] -> "apple" is in dictionary -> end

Result: True

Flow:
┌─────────────┐
│ Start (0)   │
└─────┬───────┘
      │ "apple" found
┌─────▼───────┐
│ Check (5)   │
└─────┬───────┘
      │ "pen" found
┌─────▼───────┐
│ Check (8)   │
└─────┬───────┘
      │ "apple" found
┌─────▼───────┐
│ End (13)    │
└─────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the Word Break Problem asks and how input is structured.

You have a string and a list of words (dictionary). The goal is to find if the string can be split into words from the dictionary without leftover characters. For example, "catsanddog" with dictionary {"cat", "cats", "and", "sand", "dog"} can be split as "cats" + "and" + "dog".

Result

You understand the problem statement and what inputs and outputs look like.

Understanding the problem clearly is the first step to solving it correctly and efficiently.

2

Foundation

Brute Force Recursive Approach

Concept: Try all possible splits recursively to check if the string can be segmented.

Start from the beginning of the string. For each position, check if the substring from start to that position is in the dictionary. If yes, recursively check the rest of the string. If any path leads to the end, return true. Otherwise, false. Example: For "applepenapple", check "a", "ap", "app", ... "apple" (found), then check "penapple" recursively.

Result

The method works but is slow because it repeats checks for the same substrings many times.

Knowing the brute force method helps you see why optimization is needed to avoid repeated work.

3

Intermediate

Dynamic Programming Memoization

🤔Before reading on: do you think storing results of substring checks will speed up the solution or not? Commit to your answer.

Concept: Use a memory structure to save results of substring checks to avoid repeated work.

Create an array or map to remember if a substring starting at a certain index can be segmented. When you check a substring, save the result. If you need to check it again, use the saved result instead of recomputing. This reduces the time from exponential to polynomial.

Result

The solution becomes much faster and can handle longer strings efficiently.

Understanding memoization is key to solving many problems that involve repeated subproblems.

4

Intermediate

Bottom-Up Dynamic Programming

🤔Before reading on: do you think starting from the end of the string or the beginning is better for building the solution? Commit to your answer.

Concept: Build the solution from smaller substrings up to the full string using a table.

Create a boolean array dp of size n+1 where dp[i] means the substring from i to end can be segmented. Initialize dp[n] = true (empty string). Fill dp from the end to the start. For each position i, check all substrings s[i:j]. If s[i:j] is in dictionary and dp[j] is true, set dp[i] = true. Example: For "applepenapple", dp[13] = true, then check backwards.

Result

You get a clear, iterative way to solve the problem efficiently without recursion.

Bottom-up DP helps visualize how smaller solutions combine to solve the bigger problem.

5

Intermediate

Handling Large Dictionaries Efficiently

🤔Before reading on: do you think checking every substring against the dictionary is efficient for large dictionaries? Commit to your answer.

Concept: Optimize dictionary lookups to speed up substring checks.

Instead of checking every substring against the dictionary, use a hash set for O(1) lookups. Also, limit substring lengths to the maximum word length in the dictionary to reduce unnecessary checks. This reduces the number of checks and speeds up the algorithm.

Result

The solution runs faster on large inputs with big dictionaries.

Optimizing data structures used for lookups can drastically improve performance.

6

Advanced

Reconstructing the Word Sequence

🤔Before reading on: do you think the Word Break Problem only asks for yes/no or can it also return the actual words? Commit to your answer.

Concept: Extend the solution to not only check if segmentation is possible but also return one valid sequence of words.

Modify the DP to store the index where the valid word ends. After filling dp, backtrack from start using stored indices to build the sequence of words. Example: For "applepenapple", backtrack to get ["apple", "pen", "apple"].

Result

You can output the actual words that form the string, not just true/false.

Knowing how to reconstruct solutions from DP tables is crucial for many real-world problems.

7

Expert

Advanced Optimizations and Trie Usage

🤔Before reading on: do you think using a Trie data structure can improve dictionary lookups? Commit to your answer.

Concept: Use a Trie (prefix tree) to efficiently check prefixes and reduce substring checks.

Build a Trie from the dictionary words. While checking substrings, traverse the Trie instead of checking each substring separately. This allows early stopping when no word matches the prefix. This reduces unnecessary substring checks and speeds up the algorithm, especially for large dictionaries with common prefixes.

Result

The algorithm becomes more efficient and scalable for large inputs.

Using specialized data structures like Tries can optimize common operations and improve performance beyond basic DP.

Under the Hood

The Word Break Problem uses dynamic programming to break a large problem into smaller overlapping subproblems. Internally, it stores results of substring checks in a table to avoid recomputation. The algorithm iterates over the string, checking substrings against the dictionary using fast lookups. When using a Trie, it traverses nodes representing prefixes to quickly reject invalid paths.

Why designed this way?

The problem was designed to test efficient string segmentation. Early brute force methods were too slow due to repeated checks. Dynamic programming was introduced to store intermediate results and reduce time complexity. Tries were added later to optimize prefix checks, especially for large dictionaries with many words sharing prefixes.

┌───────────────┐
│ Input String  │
└──────┬────────┘
       │
┌──────▼────────┐
│ Dictionary    │
│ (HashSet/Trie)│
└──────┬────────┘
       │
┌──────▼────────┐
│ DP Table      │
│ (Boolean Array│
│  or Memo Map) │
└──────┬────────┘
       │
┌──────▼────────┐
│ Result       │
│ (True/False) │
│ or Word List │
└──────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the Word Break Problem always require returning the actual words? Commit yes or no.

Common Belief: The problem always asks to return the sequence of words that form the string.

Reality: The basic Word Break Problem only asks if the string can be segmented (true/false). Returning the actual words is an extension called Word Break II.

Why it matters: Confusing these leads to writing more complex code than needed or misunderstanding problem requirements.

Quick: Do you think checking every substring against the dictionary is efficient for large inputs? Commit yes or no.

Common Belief: Checking every possible substring against the dictionary is efficient enough.

Reality: Checking all substrings without optimization leads to exponential time and is inefficient for large inputs.

Why it matters: Ignoring this causes slow programs that time out or crash on big data.

Quick: Is it true that dynamic programming always uses bottom-up approach? Commit yes or no.

Common Belief: Dynamic programming solutions must be bottom-up and cannot be recursive.

Reality: Dynamic programming can be implemented top-down with memoization (recursive) or bottom-up iteratively. Both are valid.

Why it matters: Believing this limits problem-solving approaches and understanding of DP.

Quick: Do you think using a Trie is always slower than a hash set for dictionary lookups? Commit yes or no.

Common Belief: Hash sets are always faster than Tries for dictionary lookups.

Reality: Tries can be faster when many words share prefixes because they avoid redundant checks and allow early pruning.

Why it matters: Choosing the wrong data structure can hurt performance in large-scale applications.

Expert Zone

1

DP table size and substring checks can be optimized by limiting substring length to the longest dictionary word.

2

Memoization top-down and bottom-up DP have different memory and call stack implications; choosing depends on problem constraints.

3

Trie traversal combined with DP can prune impossible paths early, reducing time complexity significantly.

When NOT to use

Avoid using Word Break DP when the dictionary is extremely large and dynamic, or when approximate matches are needed. Instead, use probabilistic models or machine learning for fuzzy matching.

Production Patterns

In production, Word Break is used in text input validation, autocomplete systems, and natural language processing pipelines. Often combined with tries and caching layers for speed.

Connections

Dynamic Programming

Word Break is a classic example of dynamic programming applied to strings.

Understanding Word Break deepens your grasp of DP principles like overlapping subproblems and optimal substructure.

Trie Data Structure

Tries optimize prefix searches needed in Word Break.

Knowing Tries helps you improve dictionary lookups and prune search space efficiently.

Natural Language Processing (NLP)

Word Break relates to tokenization, a fundamental NLP task.

Understanding Word Break algorithms helps in building better text parsers and language models.

Common Pitfalls

#1 Checking all substrings without limiting length causes slow performance.

Wrong approach:

for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (dict.count(s.substr(i, j - i)) && dp[j]) {
dp[i] = true;
}
}
}

Correct approach:

int maxLen = maxWordLengthInDict;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n && j - i <= maxLen; j++) {
if (dict.count(s.substr(i, j - i)) && dp[j]) {
dp[i] = true;
break;
}
}
}

Root cause:

Not considering dictionary word length leads to unnecessary substring checks.

#2 Not using memoization causes repeated work and exponential time.

Wrong approach:

bool wordBreak(string s, unordered_set& dict) {
if (s.empty()) return true;
for (int i = 1; i <= s.size(); i++) {
if (dict.count(s.substr(0, i)) && wordBreak(s.substr(i), dict))
return true;
}
return false;
}

Correct approach:

unordered_map memo;
bool wordBreak(string s, unordered_set& dict) {
if (s.empty()) return true;
if (memo.count(s)) return memo[s];
for (int i = 1; i <= s.size(); i++) {
if (dict.count(s.substr(0, i)) && wordBreak(s.substr(i), dict)) {
memo[s] = true;
return true;
}
}
memo[s] = false;
return false;
}

Root cause:

Ignoring memoization causes repeated recursive calls on the same substrings.

#3 Confusing problem requirements by trying to return words when only yes/no is needed.

Wrong approach:

bool wordBreak(string s, unordered_set& dict) {
// code that tries to build and return vector but problem expects bool
}

Correct approach:

bool wordBreak(string s, unordered_set& dict) {
// code that returns true or false only
}

Root cause:

Misunderstanding problem statement leads to overcomplicated or incorrect solutions.

Key Takeaways

The Word Break Problem checks if a string can be split into valid dictionary words without leftovers.

Dynamic programming avoids repeated work by storing results of substring checks, making the solution efficient.

Using data structures like hash sets and tries optimizes dictionary lookups and speeds up the algorithm.

The problem can be extended to reconstruct the actual sequence of words, not just a yes/no answer.

Understanding Word Break deepens your grasp of string processing and dynamic programming techniques.

Practice

1. What does the Word Break Problem ask you to determine about a given string s and a dictionary of words wordDict?

easy

A. If s is exactly equal to one of the words in wordDict

B. If s contains any substring from wordDict

C. If s can be segmented into a space-separated sequence of one or more dictionary words

D. If s is a palindrome formed by dictionary words

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks if the entire string s can be split into parts where each part is a word from the dictionary wordDict.

2. Step 2: Differentiate from similar concepts

   It is not enough for s to contain a dictionary word or be equal to one; the whole string must be fully segmented into dictionary words.

3. Final Answer:

   If s can be segmented into a sequence of dictionary words -> Option C

4. Quick Check:

   Word Break = Full segmentation check [OK]

Hint: Check if full string splits into dictionary words [OK]

Common Mistakes:

• Thinking partial substring match is enough
• Confusing exact match with segmentation
• Ignoring the order of words in segmentation

2. Which of the following is the correct C++ syntax to declare a function named wordBreak that takes a string s and a vector<string> named wordDict and returns a bool?

easy

A. bool wordBreak(string s, vector<string> &wordDict);

B. bool wordBreak(string s, vector<string>& wordDict);

C. bool wordBreak(string s, vector<string> wordDict);

D. bool wordBreak(string s, vector<string> wordDict&);

Solution

1. Step 1: Understand parameter passing in C++

   Passing vector<string> by reference requires the ampersand & after the type, with optional space before the variable name.

2. Step 2: Check syntax correctness

   bool wordBreak(string s, vector<string> &wordDict); correctly places the ampersand before the parameter name with a space: vector<string> &wordDict. bool wordBreak(string s, vector<string>& wordDict); is also valid but less common spacing. bool wordBreak(string s, vector<string> wordDict&); is invalid syntax.

3. Final Answer:

   bool wordBreak(string s, vector<string> &wordDict); -> Option A

4. Quick Check:

   Reference parameter syntax = bool wordBreak(string s, vector<string> &wordDict); [OK]

Hint: Ampersand & goes between type and variable name [OK]

Common Mistakes:

• Placing & after variable name incorrectly
• Missing semicolon at function declaration
• Using invalid syntax like wordDict&

3. What is the output of the following C++ code snippet?

bool wordBreak(string s, vector<string> &wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

int main() {
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    cout << (wordBreak(s, wordDict) ? "true" : "false") << endl;
    return 0;
}

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand the dynamic programming logic

   The code uses a boolean vector dp where dp[i] is true if substring s[0..i-1] can be segmented into dictionary words. It initializes dp[0] as true (empty string).

2. Step 2: Trace the example input "leetcode" with dictionary ["leet", "code"]

   At i=4, substring "leet" is in dictionary, so dp[4] = true. At i=8, substring "code" is in dictionary and dp[4] is true, so dp[8] = true. Finally, dp[s.size()] = true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   DP segmentation confirms full string = true [OK]

Hint: Check dp array for full string index true [OK]

Common Mistakes:

• Confusing substring indices
• Forgetting to break inner loop after true
• Misunderstanding dp initialization

4. Identify the bug in the following C++ code for the Word Break Problem:

bool wordBreak(string s, vector<string> &wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size(), false);
    dp[0] = true;
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

medium

A. dp[0] should be initialized to false

B. dp vector size should be s.size() + 1, not s.size()

C. The substring indices in s.substr are incorrect

D. unordered_set should be a vector instead

Solution

1. Step 1: Check dp vector size and indexing

   The dp vector is sized to s.size(), but the code accesses dp[s.size()] which is out of bounds. It should be sized s.size() + 1 to include the base case for empty substring.

2. Step 2: Verify other parts

   unordered_set usage and substring indices are correct. dp[0] must be true to represent empty string segmentation.

3. Final Answer:

   dp vector size should be s.size() + 1, not s.size() -> Option B

4. Quick Check:

   dp size off by one causes runtime error [OK]

Hint: dp size = string length + 1 for base case [OK]

Common Mistakes:

• Using dp size equal to string length only
• Misinitializing dp[0] to false
• Confusing substring parameters

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which of the following modifications to the Word Break algorithm allows it to also return the actual segmented sentence "apple pen apple" instead of just true or false?

hard

A. Use a stack to store indices and print words in reverse order after DP

B. Return the count of possible segmentations instead of a boolean

C. Modify the dictionary to include spaces between words

D. Use a vector of strings to store sentences at each index and build them during DP

Solution

1. Step 1: Understand the limitation of boolean DP

   The standard Word Break DP returns only true/false indicating if segmentation is possible, but does not store the actual segmented sentences.

2. Step 2: Modify DP to store sentences

   By using a vector of strings at each dp index, we can store all possible sentences formed up to that index. When a valid word is found, append it to sentences from previous indices.

3. Step 3: Final answer

   This approach allows reconstructing the segmented sentence like "apple pen apple".

4. Final Answer:

   Use a vector of strings to store sentences at each index and build them during DP -> Option D

5. Quick Check:

   Store sentences in DP to reconstruct output [OK]

Hint: Store sentences in DP array to reconstruct segmentation [OK]

Common Mistakes:

• Trying to modify dictionary words
• Returning count instead of sentences
• Using stack without DP sentence storage