Word Break Problem in DSA Go - Execution Trace

Concept Flow - Word Break Problem

Start with empty string

↓

Check prefixes in dictionary

↓

If prefix found

↓

Recursively check suffix

↓

Suffix can be segmented?

↓

Mark position True

↓

Reach end of string?

↓

Return True

The flow checks prefixes of the string against the dictionary. If a prefix matches, it recursively checks the remaining suffix. If the suffix can be segmented, it marks the position as true and continues until the whole string is segmented or no options remain.

Execution Sample

DSA Go

func wordBreak(s string, wordDict []string) bool {
    wordSet := make(map[string]bool)
    for _, word := range wordDict {
        wordSet[word] = true
    }
    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] && wordSet[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}

This code uses a set for fast dictionary lookup and a boolean array dp to track if substrings s[0:i] can be segmented into words from the dictionary. It iterates over the string positions i, and for each possible split point j < i, checks if the prefix s[0:j] is segmentable (dp[j]) and s[j:i] is in the dictionary (wordSet). If yes, marks dp[i] true and breaks early.

Execution Table

Step	Operation	i	j	Substring s[j:i]	dp Array State	Action
1	Initialize dp	-	-	-	[true, false, false, false, false, false, false, false, false]	dp[0] = true (empty string)
2	i=1, j=0	1	0	"l"	[true, false, false, false, false, false, false, false, false]	Not in dict, dp[1] stays false
3	i=2, j=0	2	0	"le"	[true, false, false, false, false, false, false, false, false]	Not in dict, dp[2] stays false
4	i=2, j=1	2	1	"e"	[true, false, false, false, false, false, false, false, false]	Not in dict, dp[2] stays false
5	i=3, j=0	3	0	"lee"	[true, false, false, false, false, false, false, false, false]	Not in dict, dp[3] stays false
6	i=3, j=1	3	1	"ee"	[true, false, false, false, false, false, false, false, false]	Not in dict, dp[3] stays false
7	i=3, j=2	3	2	"e"	[true, false, false, false, false, false, false, false, false]	Not in dict, dp[3] stays false
8	i=4, j=0	4	0	"leet"	[true, false, false, false, true, false, false, false, false]	In dict and dp[0] true, dp[4] = true
9	i=5, j=0	5	0	"leetc"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[5] stays false
10	i=5, j=1	5	1	"eetc"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[5] stays false
11	i=5, j=2	5	2	"etc"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[5] stays false
12	i=5, j=3	5	3	"tc"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[5] stays false
13	i=5, j=4	5	4	"c"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[5] stays false
14	i=6, j=0	6	0	"leetco"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[6] stays false
15	i=6, j=1	6	1	"eetco"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[6] stays false
16	i=6, j=2	6	2	"etco"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[6] stays false
17	i=6, j=3	6	3	"tco"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[6] stays false
18	i=6, j=4	6	4	"co"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[6] stays false
19	i=6, j=5	6	5	"o"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[6] stays false
20	i=7, j=0	7	0	"leetcod"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[7] stays false
21	i=7, j=1	7	1	"eetcod"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[7] stays false
22	i=7, j=2	7	2	"etcod"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[7] stays false
23	i=7, j=3	7	3	"tcod"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[7] stays false
24	i=7, j=4	7	4	"cod"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[7] stays false
25	i=7, j=5	7	5	"od"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[7] stays false
26	i=7, j=6	7	6	"d"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[7] stays false
27	i=8, j=0	8	0	"leetcode"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[8] stays false
28	i=8, j=1	8	1	"eetcode"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[8] stays false
29	i=8, j=2	8	2	"etcode"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[8] stays false
30	i=8, j=3	8	3	"tcode"	[true, false, false, false, true, false, false, false, false]	Not in dict, dp[8] stays false
31	i=8, j=4	8	4	"code"	[true, false, false, false, true, false, false, false, true]	In dict and dp[4] true, dp[8] = true
32	End	-	-	-	[true, false, false, false, true, false, false, false, true]	dp[len(s)] = true, string can be segmented

💡 Reached end of string with dp[len(s)] = true, meaning string can be segmented into dictionary words

Variable Tracker

Variable	Start	After i=1	After i=2	After i=3	After i=4	After i=5	After i=6	After i=7	After i=8	Final
dp	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, true]	[true, false, false, false, true, false, false, false, true]

Key Moments - 3 Insights

Why do we set dp[0] = true at the start?

dp[0] = true means the empty string can be segmented. This is the base case allowing the algorithm to build solutions for longer substrings, as shown in step 1 of the execution_table.

Why do we check dp[j] before checking if s[j:i] is in the dictionary?

We only check s[j:i] if dp[j] is true because dp[j] means the substring s[0:j] can be segmented. This avoids unnecessary checks and ensures we only build on valid segmentations, as seen in steps 8 and 31.

What does it mean when dp[i] becomes true?

dp[i] = true means the substring s[0:i] can be segmented into dictionary words. This is the key to solving the problem, and the final answer is dp[len(s)], as shown in step 32.

Visual Quiz - 3 Questions

Look at the execution_table at step 8. What is the substring s[j:i] checked and why does dp[4] become true?

A "leet" is in the dictionary and dp[0] is true

B "leet" is not in the dictionary but dp[0] is true

C "leet" is in the dictionary but dp[0] is false

D "leet" is not in the dictionary and dp[0] is false

💡 Hint

Check the substring column and dp array state at step 8 in execution_table

At which step does dp[len(s)] become true indicating the whole string can be segmented?

A Step 14

B Step 32

C Step 31

D Step 8

💡 Hint

Look at the dp array state and action in step 31 of execution_table

If the dictionary did not contain "code", what would happen to dp[8] in the execution_table?

A dp[8] would still become true at step 31

B dp[8] would remain false after all checks

C dp[4] would become false instead

D dp[0] would become false

💡 Hint

Refer to step 31 where dp[8] is set true because "code" is in the dictionary

Concept Snapshot

Word Break Problem:
- Use dp array of bool size len(s)+1
- dp[0] = true (empty string)
- For each i, check all j < i
- If dp[j] true and s[j:i] in dict, dp[i] = true
- Result is dp[len(s)]
- Time: O(n^2 * k), k = max word length

Full Transcript

The Word Break Problem checks if a string can be split into dictionary words. We use a boolean array dp where dp[i] means substring s[0:i] can be segmented. Start with dp[0] = true for empty string. For each position i, check all prefixes s[j:i]. If dp[j] is true and s[j:i] is in the dictionary, set dp[i] true. Continue until dp[len(s)] tells if full string can be segmented. The execution table shows each substring checked and dp updates. Key moments clarify why dp[0] is true, why dp[j] is checked first, and what dp[i] true means. The visual quiz tests understanding of substring checks, dp updates, and dictionary impact. This approach efficiently solves the problem using dynamic programming.

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