Word Break Problem in DSA Python - Execution Trace

Concept Flow - Word Break Problem

Start with full string

↓

Check prefixes in dictionary

↓

Split string

↓

Recursively check suffix

↓

If suffix empty, return True

↓

Combine results

↓

Return final True/False

Try to split the string into dictionary words by checking prefixes and recursively verifying suffixes until the whole string is segmented or no valid split is found.

Execution Sample

DSA Python

def word_break(s, word_dict):
    if not s:
        return True
    for i in range(1, len(s)+1):
        if s[:i] in word_dict and word_break(s[i:], word_dict):
            return True
    return False

This code checks if the string can be segmented into words from the dictionary by trying all prefixes and recursively checking the remaining suffix.

Execution Table

Step	Operation	Current String	Prefix Checked	Is Prefix in Dict?	Recursive Call on Suffix	Result	Visual State
1	Check full string 'leetcode'	leetcode	l	No	-	False	[]
2	Check prefix 'le'	leetcode	le	No	-	False	[]
3	Check prefix 'lee'	leetcode	lee	No	-	False	[]
4	Check prefix 'leet'	leetcode	leet	Yes	word_break('code')	-	[]
5	Recursive call: check 'code'	code	c	No	-	False	[]
6	Check prefix 'co'	code	co	No	-	False	[]
7	Check prefix 'cod'	code	cod	No	-	False	[]
8	Check prefix 'code'	code	code	Yes	word_break('')	-	[]
9	Recursive call: check '' (empty)		-	-	-	True	[]
10	Return True for 'code'	code	code	Yes	True	True	[]
11	Return True for 'leetcode'	leetcode	leet	Yes	True	True	[]
12	Final result	leetcode	-	-	-	True	[]

💡 All prefixes checked or valid segmentation found; recursion ends with True for 'leetcode'

Variable Tracker

Variable	Start	After Step 4	After Step 8	After Step 9	Final
s	leetcode	code	code		leetcode
prefix	-	leet	code	-	leet/code
result	-	-	-	True	True

Key Moments - 3 Insights

Why do we return True when the string is empty?

Because an empty string means all parts have been successfully segmented, as shown in step 9 where word_break('') returns True.

Why do we check all prefixes instead of just one?

Because the string can be split in multiple ways, we must try all prefixes to find a valid segmentation, as seen in steps 1-4 where prefixes 'l', 'le', 'lee' fail but 'leet' succeeds.

What happens if no prefix matches the dictionary?

The function returns False after checking all prefixes, as in steps 1-3 and 5-7 where no valid prefix is found, leading to backtracking.

Visual Quiz - 3 Questions

Look at the execution table, what is the result of the recursive call on suffix 'code' at step 8?

A True

B False

C Not evaluated

D Error

💡 Hint

Check the 'Result' column at step 8 and the recursive call on suffix 'code'

At which step does the function return True for the original string 'leetcode'?

A Step 9

B Step 11

C Step 4

D Step 1

💡 Hint

Look at the 'Result' column and the 'Current String' for 'leetcode'

If the dictionary did not contain 'leet', what would happen at step 4?

A Return True immediately

B Check next prefix

C Return False immediately

D Skip prefix checking

💡 Hint

Refer to the 'Is Prefix in Dict?' column at step 4 and what happens when prefix is not found

Concept Snapshot

Word Break Problem:
- Check all prefixes of string
- If prefix in dictionary, recursively check suffix
- If suffix empty, return True
- Else backtrack and try next prefix
- Return True if any segmentation works, else False

Full Transcript

The Word Break Problem tries to split a string into valid dictionary words. We check every prefix of the string. If the prefix is in the dictionary, we recursively check the remaining suffix. If the suffix is empty, it means the entire string can be segmented, so we return True. If no prefix leads to a valid segmentation, we return False. This process uses recursion and backtracking to explore all possible splits.

Practice

1. What is the main goal of the Word Break Problem in algorithms?

easy

A. To check if a string can be segmented into a sequence of dictionary words

B. To find the longest word in a dictionary

C. To count the number of vowels in a string

D. To reverse the words in a sentence

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: Match the goal with options

   To check if a string can be segmented into a sequence of dictionary words correctly describes this goal, while others describe unrelated tasks.

3. Final Answer:

   To check if a string can be segmented into a sequence of dictionary words -> Option A

4. Quick Check:

   Word Break Problem = Check segmentation [OK]

Hint: Remember: Word Break checks if string splits into dictionary words [OK]

Common Mistakes:

• Confusing Word Break with string reversal
• Thinking it counts vowels or finds longest word
• Assuming it modifies the string instead of checking segmentation

2. Which of the following is the correct Python syntax to check if a substring s[:i] is in a dictionary wordDict inside a loop?

easy

A. if s[:i] contains wordDict:

B. if s[:i] in wordDict:

C. if wordDict in s[:i]:

D. if s[:i] == wordDict:

Solution

1. Step 1: Understand Python membership syntax

   To check if an element is in a collection, use element in collection.

2. Step 2: Apply to substring and dictionary

   We want to check if substring s[:i] is in wordDict, so if s[:i] in wordDict: is correct.

3. Final Answer:

   if s[:i] in wordDict: -> Option B

4. Quick Check:

   Membership test uses 'in' keyword [OK]

Hint: Use 'in' keyword to check membership in Python [OK]

Common Mistakes:

• Using 'contains' instead of 'in'
• Reversing order of operands in membership test
• Using equality '==' instead of membership

3. What will be the output of the following code snippet?

def wordBreak(s, wordDict):
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordDict:
                dp[i] = True
                break
    return dp[-1]

print(wordBreak('applepenapple', {'apple', 'pen'}))

medium

A. False

B. null

C. SyntaxError

D. True

Solution

1. Step 1: Understand the dynamic programming approach

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

2. Step 2: Trace the input 'applepenapple'

   'apple' and 'pen' are in the dictionary. The string can be segmented as 'apple' + 'pen' + 'apple', so dp[-1] becomes True.

3. Final Answer:

   True -> Option D

4. Quick Check:

   String segments into dictionary words = True [OK]

Hint: Check if dp array ends with True for full string segmentation [OK]

Common Mistakes:

• Assuming false because of nested loops
• Confusing dp indices and substring slicing
• Ignoring the break statement after true found

4. Identify the error in the following code snippet for the Word Break Problem:

def wordBreak(s, wordDict):
    dp = [False] * len(s)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in wordDict:
                dp[i] = True
    return dp[-1]

medium

A. dp list size is incorrect; should be len(s) + 1

B. Missing return statement

C. Using 'and' instead of '&' in condition

D. Loop ranges are reversed

Solution

1. Step 1: Check dp list initialization

   dp should have length len(s) + 1 to include dp[0] for empty string and dp[len(s)] for full string.

2. Step 2: Identify impact of incorrect dp size

   With dp size len(s), dp[i] access when i == len(s) causes index error or incorrect logic.

3. Final Answer:

   dp list size is incorrect; should be len(s) + 1 -> Option A

4. Quick Check:

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

Hint: dp array must be length string+1 for indexing [OK]

Common Mistakes:

• Initializing dp with length len(s) only
• Forgetting dp[0] represents empty string
• Not breaking loop after setting dp[i] true

5. Given the string s = 'catsanddog' and dictionary wordDict = {'cat', 'cats', 'and', 'sand', 'dog'}, which of the following lists contains all possible valid segmentations of s?

hard

A. ['cat and dog', 'cats sand dog']

B. ['cat sanddog', 'catsand dog']

C. ['cats and dog', 'cat sand dog']

D. ['catsanddog']

Solution

1. Step 1: Identify valid dictionary words in the string

   Words 'cat', 'cats', 'and', 'sand', 'dog' are in the dictionary.

2. Step 2: Find segmentations matching dictionary words

   Possible splits: 'cats' + 'and' + 'dog' and 'cat' + 'sand' + 'dog' are valid segmentations.

3. Final Answer:

   ['cats and dog', 'cat sand dog'] -> Option C

4. Quick Check:

   All segments are dictionary words [OK]

Hint: Split string using all dictionary words to find valid sentences [OK]

Common Mistakes:

• Ignoring valid splits and choosing whole string
• Mixing invalid word splits
• Confusing word boundaries