Word Break Problem in DSA Python

Mental Model

We want to check if a long word can be split into smaller valid words from a dictionary. We try breaking it step by step and remember what parts can be formed.

Analogy: Imagine you have a long sentence without spaces and a list of known words. You try to put spaces in places so that every piece is a known word, like solving a puzzle by fitting pieces together.

s t r i n g
↑
Dictionary: ["cat", "cats", "and", "sand", "dog"]

Dry Run Walkthrough

Input: string: "catsanddog", dictionary: ["cat", "cats", "and", "sand", "dog"]

Goal: Check if "catsanddog" can be split into words from the dictionary

Step 1: Check prefix "cat" (index 0 to 2) in dictionary

"cat" is in dictionary, mark position 3 as reachable

Why: If prefix is a word, we can try to break the rest starting from index 3

Step 2: Check prefix "cats" (index 0 to 3) in dictionary

"cats" is in dictionary, mark position 4 as reachable

Why: Another valid prefix, so index 4 is also a valid break point

Step 3: From index 3, check substring "sand" (3 to 6) in dictionary

"sand" is in dictionary, mark position 7 as reachable

Why: From previous break at 3, "sand" is a valid word, so index 7 is reachable

Step 4: From index 4, check substring "and" (4 to 6) in dictionary

"and" is in dictionary, mark position 7 as reachable

Why: From previous break at 4, "and" is a valid word, so index 7 is reachable

Step 5: From index 7, check substring "dog" (7 to 9) in dictionary

"dog" is in dictionary, mark position 10 as reachable (end of string)

Why: Last part is a valid word, so whole string can be segmented

Result:

"catsanddog" can be segmented as "cats and dog" or "cat sand dog"

Annotated Code

DSA Python

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)  # Convert list to set for fast lookup
        n = len(s)
        dp = [False] * (n + 1)  # dp[i] means s[:i] can be segmented
        dp[0] = True  # empty string can be segmented

        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[n]

# Driver code
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
sol = Solution()
print(sol.wordBreak(s, wordDict))

dp = [False] * (n + 1) # dp[i] means s[:i] can be segmented

Initialize dp array to track which prefixes can be segmented

dp[0] = True # empty string can be segmented

Base case: empty string is always segmentable

for i in range(1, n + 1):

Check all prefixes ending at i

for j in range(i):

Try all possible breaks between j and i

if dp[j] and s[j:i] in word_set:

If prefix up to j is segmentable and s[j:i] is a word, mark dp[i]

dp[i] = True

Mark prefix ending at i as segmentable

return dp[n]

Return if whole string can be segmented

Output

True

Complexity Analysis

Time: O(n^2) because for each position i, we check all j < i to find valid breaks

Space: O(n) for the dp array storing segmentation states for each prefix

vs Alternative: Naive recursion tries all splits repeatedly causing exponential time; DP remembers results to reduce to polynomial time

Edge Cases

Empty string s = ""

Returns True because empty string can be segmented trivially

DSA Python

dp[0] = True  # empty string can be segmented

String with no valid segmentation

Returns False because no combination of dictionary words forms the string

DSA Python

if dp[j] and s[j:i] in word_set:

String equals a single dictionary word

Returns True immediately as whole string is a word

DSA Python

if dp[j] and s[j:i] in word_set:

When to Use This Pattern

When asked if a string can be split into dictionary words, use the Word Break pattern with dynamic programming to remember valid prefixes and avoid repeated work.

Common Mistakes

Mistake: Not using a dp array to remember which prefixes are valid, causing repeated checks and slow code
Fix: Use a boolean dp array where dp[i] means s[:i] can be segmented, and build it up from smaller prefixes

Mistake: Checking substrings without verifying if the prefix before it is valid
Fix: Only check s[j:i] if dp[j] is True, meaning prefix s[:j] can be segmented

Summary

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

Use when you need to verify if a string can be segmented into known words efficiently.

Remember to build solutions from smaller prefixes and store results to avoid repeated work.

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