Word Break Problem in DSA Python - Build from Scratch

Word Break Problem

📖 Scenario: Imagine you have a long string of letters without spaces. You want to check if you can split this string into words that you know from a dictionary.This is like when you see a long word puzzle and want to find if it can be broken into smaller known words.

🎯 Goal: You will write a program that checks if a given string can be segmented into a sequence of dictionary words.

📋 What You'll Learn

Create a string variable called input_string with the exact value "applepenapple".

Create a list called word_dict with the exact words "apple" and "pen".

Write a function called word_break that takes input_string and word_dict and returns True if the string can be segmented into dictionary words, otherwise False.

Print the result of calling word_break(input_string, word_dict).

💡 Why This Matters

🌍 Real World

This problem is useful in text processing, such as checking if a sentence without spaces can be split into valid words.

💼 Career

Understanding this problem helps in roles involving natural language processing, search engines, and coding interviews.

1

Create the input string and dictionary list

Create a string variable called input_string with the exact value "applepenapple". Create a list called word_dict with the exact words "apple" and "pen".

DSA Python

# Create input_string and word_dict variables
# Your code here

Hint

Use = to assign the string and list exactly as shown.

2

Define the word_break function

Define a function called word_break that takes two parameters: s and word_dict. Inside the function, create a list called dp with length len(s) + 1 filled with False. Set dp[0] to True.

DSA Python

input_string = "applepenapple"
word_dict = ["apple", "pen"]

# Define the word_break function with parameters s and word_dict
# Your code here

Hint

Use def to define the function and create the dp list with False values.

3

Implement the core logic to fill dp list

Inside the word_break function, add a for loop with variable i from 1 to len(s) inclusive. Inside it, add another for loop with variable j from 0 to i. Inside the inner loop, check if dp[j] is True and if s[j:i] is in word_dict. If both are true, set dp[i] to True and break the inner loop. After the loops, return dp[len(s)].

DSA Python

input_string = "applepenapple"
word_dict = ["apple", "pen"]

def word_break(s, word_dict):
    dp = [False] * (len(s) + 1)
    dp[0] = True
    # Add nested for loops to fill dp list
    # Your code here

Hint

Use two loops to check all substrings and update dp accordingly.

4

Print the result of word_break function

Print the result of calling word_break(input_string, word_dict).

DSA Python

input_string = "applepenapple"
word_dict = ["apple", "pen"]

def word_break(s, word_dict):
    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 word_dict:
                dp[i] = True
                break
    return dp[len(s)]

# Print the result of word_break function
# Your code here

Hint

Use print() to show the result of the function call.

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