Word Break Problem in DSA Go - 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. It checks whether the string can be segmented so that every piece is a word you know. This helps in understanding how to break down complex strings into meaningful parts.

Why it matters

Without this concept, computers would struggle to understand or process text without clear spaces, like in languages or codes where words run together. It solves the problem of recognizing meaningful words inside a long string, which is essential for text processing, search engines, and language understanding.

Where it fits

Before this, you should know about strings and basic data structures like arrays or sets. After this, you can learn about dynamic programming, recursion optimization, and more complex text algorithms like autocomplete or spell checking.

Mental Model

Core Idea

The Word Break Problem is about checking if a string can be split into smaller valid words from a dictionary, using a step-by-step approach to test all possible breaks.

Think of it like...

Imagine you have a long necklace made of beads without any gaps, and you want to see if you can cut it into smaller necklaces where each smaller necklace is a known pattern you recognize.

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

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

Result: YES, string can be segmented.

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Statement

Concept: Learn what the Word Break Problem asks and what inputs it takes.

The problem gives you a string and a list of words (dictionary). Your task is to find out if you can split the string into words from the dictionary without leftover letters. For example, "catsanddog" with dictionary {"cat", "cats", "and", "sand", "dog"} can be split as "cats and dog" or "cat sand dog".

Result

You understand the input and output: input is a string and dictionary; output is true or false if segmentation is possible.

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

2

Foundation

Basic String and Dictionary Setup

Concept: Learn how to represent the string and dictionary in code.

In Go, the string is a simple variable. The dictionary can be stored as a map[string]bool for quick lookups. For example: words := map[string]bool{"cat": true, "cats": true, "and": true, "sand": true, "dog": true} This lets you check if a substring is a valid word quickly.

Result

You can quickly check if any substring is in the dictionary.

Using a map for the dictionary makes word lookups fast, which is crucial for performance.

3

Intermediate

Recursive Approach with Backtracking

🤔Before reading on: do you think checking all splits recursively will be efficient for long strings? Commit to yes or no.

Concept: Try splitting the string at every possible position and recursively check if the remaining string can be segmented.

Write a function that tries every prefix of the string. If the prefix is in the dictionary, recursively check the suffix. If any split leads to the end, return true. Example: func wordBreak(s string, dict map[string]bool) bool { if s == "" { return true } for i := 1; i <= len(s); i++ { prefix := s[:i] if dict[prefix] && wordBreak(s[i:], dict) { return true } } return false }

Result

The function returns true if the string can be segmented, false otherwise.

This approach shows the problem's nature but is inefficient because it repeats work for the same substrings.

4

Intermediate

Dynamic Programming Optimization

🤔Before reading on: do you think storing results of subproblems will speed up the solution? Commit to yes or no.

Concept: Use a boolean array to remember which parts of the string can be segmented to avoid repeated work.

Create a dp array where dp[i] is true if s[:i] can be segmented. Initialize dp[0] = true (empty string). For each position i, check all j < i. If dp[j] is true and s[j:i] is in dictionary, set dp[i] = true. Example: func wordBreakDP(s string, dict map[string]bool) bool { n := len(s) dp := make([]bool, n+1) dp[0] = true for i := 1; i <= n; i++ { for j := 0; j < i; j++ { if dp[j] && dict[s[j:i]] { dp[i] = true break } } } return dp[n] }

Result

The function returns true if the string can be segmented, false otherwise, much faster than recursion.

Remembering past results prevents repeated checks, making the solution efficient for large inputs.

5

Intermediate

Handling Edge Cases and Empty Strings

Concept: Learn how to handle empty strings and dictionary edge cases to avoid errors.

If the input string is empty, the answer is true because no words are needed. If the dictionary is empty, no segmentation is possible unless the string is empty. Also, check for substrings that are empty or not in dictionary to avoid false positives.

Result

The solution correctly handles empty inputs and returns expected results.

Handling edge cases prevents bugs and ensures your solution works in all scenarios.

6

Advanced

Reconstructing the Word Sequence

🤔Before reading on: do you think the DP array alone can tell you the exact words used? Commit to yes or no.

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

Use an additional array to store the index where the last valid word ends. After filling dp, backtrack from the end to reconstruct the words. Example: func wordBreakWithPath(s string, dict map[string]bool) ([]string, bool) { n := len(s) dp := make([]bool, n+1) dp[0] = true prev := make([]int, n+1) for i := range prev { prev[i] = -1 } for i := 1; i <= n; i++ { for j := 0; j < i; j++ { if dp[j] && dict[s[j:i]] { dp[i] = true prev[i] = j break } } } if !dp[n] { return nil, false } var words []string for i := n; i > 0; i = prev[i] { words = append([]string{s[prev[i]:i]}, words...) } return words, true }

Result

Returns the list of words that form the string if possible, else false.

Tracking the path during DP lets you recover the actual solution, not just the yes/no answer.

7

Expert

Time and Space Complexity Trade-offs

🤔Before reading on: do you think the DP solution always runs in linear time? Commit to yes or no.

Concept: Analyze how the length of the string and dictionary size affect performance and memory use.

The DP solution runs in O(n^2) time because for each position, it checks all previous positions. The dictionary lookup is O(1) with a map. Space is O(n) for dp arrays. For very long strings or large dictionaries, this can be costly. Optimizations include using Trie structures for dictionary or pruning impossible splits early.

Result

Understanding complexity helps decide when this solution is practical and when to optimize.

Knowing complexity trade-offs guides you to balance speed and memory for real-world problems.

Under the Hood

The solution uses dynamic programming to break the problem into smaller subproblems. It builds a boolean array where each position represents if the substring up to that point can be segmented. It relies on fast dictionary lookups to check word validity and avoids repeated work by storing results.

Why designed this way?

This approach was designed to improve on naive recursion, which repeats work exponentially. Dynamic programming trades extra memory for speed, making the problem solvable in polynomial time. Alternatives like backtracking alone are too slow for large inputs.

s = "leetcode"
Dictionary = {"leet", "code"}

Index: 0 1 2 3 4 5 6 7 8
String: l e e t c o d e

DP:    T F F F T F F F T

Steps:
- dp[0] = true (empty string)
- Check substrings:
  - "leet" (s[0:4]) in dict and dp[0] true => dp[4] = true
  - "code" (s[4:8]) in dict and dp[4] true => dp[8] = true

Result: dp[len(s)] = dp[8] = true

Myth Busters - 4 Common Misconceptions

Quick: Does the Word Break Problem always require checking every substring? Commit to yes or no.

Common Belief: You must check every possible substring to solve the problem.

Reality: Dynamic programming lets you avoid checking every substring by remembering which parts can be segmented, skipping impossible splits.

Why it matters: Without this, solutions become too slow and unusable for long strings.

Quick: Can the Word Break Problem be solved correctly without a dictionary lookup? Commit to yes or no.

Common Belief: You can solve the problem by just splitting the string without checking a dictionary.

Reality: The dictionary check is essential; without it, you can't know if a substring is a valid word.

Why it matters: Ignoring dictionary checks leads to incorrect answers and meaningless splits.

Quick: Is the recursive solution always efficient for large inputs? Commit to yes or no.

Common Belief: Recursion alone is efficient enough for all input sizes.

Reality: Recursion without memoization repeats work exponentially, causing slow performance and possible crashes.

Why it matters: Using recursion alone can cause timeouts and crashes in real applications.

Quick: Does the DP solution always use linear time? Commit to yes or no.

Common Belief: Dynamic programming solves the problem in linear time.

Reality: DP runs in quadratic time due to nested loops checking substrings, not linear.

Why it matters: Expecting linear time can lead to wrong performance assumptions and poor optimization choices.

Expert Zone

1

The choice of data structure for the dictionary (hash map vs trie) can significantly affect performance for large dictionaries.

2

Memoization in recursion can be combined with DP to optimize space or handle variations of the problem.

3

Early pruning of impossible splits based on substring length or character frequency can reduce unnecessary checks.

When NOT to use

Avoid this approach when the dictionary is extremely large or when you need to find all possible segmentations instead of just one. Alternatives include using tries for dictionary storage or backtracking with memoization for all solutions.

Production Patterns

In real systems, word break is used in text tokenization, natural language processing pipelines, and input validation. Production code often combines DP with tries and caching to handle large dictionaries and streaming inputs efficiently.

Connections

Dynamic Programming

The Word Break Problem is a classic example that builds on dynamic programming principles.

Understanding this problem deepens your grasp of how to break complex problems into overlapping subproblems and store intermediate results.

Trie Data Structure

Tries can be used to optimize dictionary lookups in the Word Break Problem.

Knowing tries helps improve performance by quickly checking prefixes, reducing unnecessary substring checks.

Human Language Processing

Word segmentation in languages without spaces uses similar logic to the Word Break Problem.

Understanding this problem connects computer algorithms to how humans parse and understand continuous speech or text.

Common Pitfalls

#1 Ignoring memoization causes repeated work and slow performance.

Wrong approach:

func wordBreak(s string, dict map[string]bool) bool {
if s == "" {
return true
}
for i := 1; i <= len(s); i++ {
prefix := s[:i]
if dict[prefix] && wordBreak(s[i:], dict) {
return true
}
}
return false
}

Correct approach:

func wordBreakMemo(s string, dict map[string]bool, memo map[string]bool) bool {
if val, ok := memo[s]; ok {
return val
}
if s == "" {
return true
}
for i := 1; i <= len(s); i++ {
prefix := s[:i]
if dict[prefix] && wordBreakMemo(s[i:], dict, memo) {
memo[s] = true
return true
}
}
memo[s] = false
return false
}

Root cause:

Not storing results of subproblems causes exponential time complexity.

#2 Using a list or array for dictionary lookups causes slow checks.

Wrong approach:

words := []string{"cat", "cats", "and", "sand", "dog"}
// Checking if substring is in words by looping every time

Correct approach:

dict := map[string]bool{"cat": true, "cats": true, "and": true, "sand": true, "dog": true}
// Check substring in O(1) time

Root cause:

Linear search in dictionary causes slow performance for large dictionaries.

#3 Not handling empty string input leads to incorrect false result.

Wrong approach:

func wordBreak(s string, dict map[string]bool) bool {
if len(s) == 0 {
return false
}
// rest of code
}

Correct approach:

func wordBreak(s string, dict map[string]bool) bool {
if len(s) == 0 {
return true
}
// rest of code
}

Root cause:

Misunderstanding that empty string means successful segmentation.

Key Takeaways

The Word Break Problem checks if a string can be split into valid dictionary words using stepwise segmentation.

Dynamic programming efficiently solves the problem by storing results of subproblems to avoid repeated work.

Using a hash map for the dictionary allows fast word lookups, which is critical for performance.

Reconstructing the actual word sequence requires tracking the segmentation path during DP.

Understanding time and space trade-offs helps optimize solutions for large inputs in real-world applications.

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 can be segmented into a space-separated sequence of one or more dictionary words

B. If s contains any substring from wordDict

C. If s is exactly equal to any word in wordDict

D. If s can be reversed to form a word in wordDict

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks if the entire string s can be split into valid words from the dictionary without leftover characters.

2. Step 2: Differentiate from similar concepts

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

3. Final Answer:

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

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 equality with segmentation
• Ignoring leftover characters after segmentation

2. Which of the following Go function signatures correctly represents a function to solve the Word Break Problem?

easy

A. func wordBreak(wordDict []string, s string) string

B. func wordBreak(s string, wordDict []string) bool

C. func wordBreak(s []string, wordDict string) int

D. func wordBreak(s string, wordDict map[string]int) []string

Solution

1. Step 1: Identify correct parameter types

   The input string s should be a string, and the dictionary wordDict should be a slice of strings.

2. Step 2: Identify correct return type

   The function returns a boolean indicating if segmentation is possible.

3. Final Answer:

   func wordBreak(s string, wordDict []string) bool -> Option B

4. Quick Check:

   Input: string + []string, Output: bool [OK]

Hint: Input string and word list, output bool [OK]

Common Mistakes:

• Swapping parameter types
• Returning wrong data type
• Using map instead of slice without reason

3. What is the output of the following Go code snippet?

func main() {
    s := "leetcode"
    wordDict := []string{"leet", "code"}
    fmt.Println(wordBreak(s, wordDict))
}

func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s)+1)
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && contains(wordDict, s[j:i]) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}

func contains(dict []string, word string) bool {
    for _, w := range dict {
        if w == word {
            return true
        }
    }
    return false
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Understand the dynamic programming approach

   The code uses a boolean slice dp where dp[i] is true if s[:i] can be segmented into dictionary words.

2. Step 2: Trace the example string "leetcode"

   "leet" and "code" are in the dictionary, so dp[len(s)] becomes true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   DP segmentation = true [OK]

Hint: Check dp array for full string length [OK]

Common Mistakes:

• Forgetting to break inner loop after true
• Incorrect substring slicing
• Not initializing dp[0] to true

4. Identify the bug in this Go code for the Word Break Problem:

func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s))
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && contains(wordDict, s[j:i]) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}

medium

A. contains function is missing

B. dp slice length is correct but dp[0] should be false

C. dp slice length should be len(s)+1 and dp[0] initialization is correct

D. Loop indices i and j are reversed

Solution

1. Step 1: Check dp slice size and initialization

   The dp slice must be of size len(s)+1 to include empty substring at index 0, and dp[0] should be true.

2. Step 2: Verify loop bounds and dp usage

   Loops use indices up to len(s), so dp must have length len(s)+1 to avoid index out of range.

3. Final Answer:

   dp slice length should be len(s)+1 and dp[0] initialization is correct -> Option C

4. Quick Check:

   dp size = len(s)+1 [OK]

Hint: dp length = string length + 1 [OK]

Common Mistakes:

• Using dp length as len(s) causes index errors
• Not initializing dp[0] to true
• Incorrect loop ranges causing panic

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which of the following modifications to the Word Break algorithm will correctly handle repeated words without extra space complexity?

hard

A. Replace dp array with a single boolean variable updated each iteration

B. Use a queue to store all possible segmentations and check each fully

C. Sort the dictionary and use binary search for substring checks

D. Use a memoization map to store results of substring checks to avoid recomputation

Solution

1. Step 1: Understand repeated word handling

   Repeated words cause repeated substring checks; memoization stores results to avoid recomputation.

2. Step 2: Analyze options for efficiency

   Memoization reduces time without increasing space beyond needed; queue or sorting do not directly optimize repeated checks; single boolean loses needed state.

3. Final Answer:

   Use a memoization map to store results of substring checks to avoid recomputation -> Option D

4. Quick Check:

   Memoization = efficient repeated checks [OK]

Hint: Memoize substring results to avoid repeated work [OK]

Common Mistakes:

• Ignoring repeated substring computations
• Using single boolean loses segmentation info
• Assuming sorting dictionary helps substring checks