Word Break Problem in DSA Go

Mental Model

We want to check if a sentence can be split into valid words from a dictionary. We try breaking the sentence at every position and see if the parts are valid.

Analogy: Imagine you have a long chain of beads with letters. You want to cut the chain into smaller pieces so that each piece is a known word, like cutting a necklace into known words.

sentence: "leetcode"
Dictionary: ["leet", "code"]

Initial:
"l" -> "e" -> "e" -> "t" -> "c" -> "o" -> "d" -> "e"

We try cuts:
"leet" | "code"

If both parts are in dictionary, success.

Dry Run Walkthrough

Input: sentence: "leetcode", dictionary: ["leet", "code"]

Goal: Determine if "leetcode" can be segmented into words from the dictionary

Step 1: Check prefix "l" - not in dictionary

"l" (no match), try next prefix

Why: Start checking from the smallest prefix to find valid words

Step 2: Check prefix "lee" - not in dictionary

"lee" (no match), try next prefix

Why: Continue checking longer prefixes for a valid word

Step 3: Check prefix "leet" - found in dictionary

"leet" (match), now check suffix "code"

Why: Found a valid word at the start, now check if rest can be segmented

Step 4: Check suffix "code" prefixes: "c", "co", "cod", "code"

"code" found in dictionary

Why: Suffix is a valid word, so whole sentence can be segmented

Result:

"leet" -> "code" -> null (true)

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func wordBreak(s string, wordDict []string) bool {
	wordSet := make(map[string]bool)
	for _, w := range wordDict {
		wordSet[w] = true
	}
	dp := make([]bool, len(s)+1)
	dp[0] = true // empty string can be segmented

	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			if dp[j] && wordSet[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}

	return dp[len(s)]
}

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

dp[0] = true // empty string can be segmented

Initialize base case: empty string is segmentable

for i := 1; i <= len(s); i++ {

Check all prefixes of s up to length i

for j := 0; j < i; j++ {

Try every split position j for prefix s[0:i]

if dp[j] && wordSet[s[j:i]] {

If s[0:j] can be segmented and s[j:i] is a word, mark s[0:i] as segmentable

dp[i] = true

Mark current prefix as segmentable

break

Stop checking further splits once segmentable

Output

true

Complexity Analysis

Time: O(n^2) because we check all substring splits for each position in the string

Space: O(n + m) where n is string length for dp array and m is dictionary size for word set

vs Alternative: Naive recursion without memoization can be exponential; DP reduces repeated work to polynomial time

Edge Cases

empty string

Returns true because empty string can be segmented trivially

DSA Go

dp[0] = true // empty string can be segmented

string with no valid segmentation

Returns false as no combination of dictionary words can form the string

DSA Go

if dp[j] && wordSet[s[j:i]] { dp[i] = true }

dictionary contains words not in string

Ignores irrelevant words, only matches valid substrings

DSA Go

wordSet := make(map[string]bool)

When to Use This Pattern

When you need to check if a string can be split into dictionary words, use dynamic programming to remember which prefixes are valid to avoid repeated checks.

Common Mistakes

Mistake: Not using a DP array to store intermediate results, causing repeated work and slow performance
Fix: Use a boolean DP array where dp[i] means s[:i] can be segmented

Mistake: Checking substrings without verifying if the prefix before it is segmentable
Fix: Ensure dp[j] is true before checking if s[j:i] is a word

Summary

Checks if a string can be split into valid dictionary words.

Use when you want to verify if a sentence can be formed by concatenating dictionary words.

Remember to use dynamic programming to store which prefixes can be segmented to avoid repeated checks.

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