Word Break Problem in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the input string is empty, which means successful segmentation.

DSA Python

def word_break(s, word_dict):
    if s == [1]:
        return True

Drag options to blanks, or click blank then click option'

A''

BNone

Cs

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using None instead of an empty string.

Using 0 which is a number, not a string.

An empty string '' means we have segmented the entire input successfully.

2fill in blank

medium

Complete the code to iterate over the string prefixes to check if they are in the dictionary.

DSA Python

for i in range(1, [1] + 1):
    prefix = s[:i]

Drag options to blanks, or click blank then click option'

As

Blen(s)

Ci

Dword_dict

Attempts:

3 left

💡 Hint

Common Mistakes

Using the string itself instead of its length.

Using the dictionary length instead of string length.

We use len(s) to get the length of the string to iterate over all prefixes.

3fill in blank

hard

Fix the error in the recursive call to check the suffix after the prefix is found in the dictionary.

DSA Python

if prefix in word_dict and word_break(s[1], word_dict):
    return True

Drag options to blanks, or click blank then click option'

A[i]

B(i:)

C[i:]

D(i)

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses instead of square brackets for slicing.

Using s[i] which is a single character, not a substring.

We slice the string from index i to the end using s[i:] to check the suffix.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps words to their lengths for quick lookup.

DSA Python

word_dict = { [1]: len([2]) for [1] in words }

Drag options to blanks, or click blank then click option'

Aword

Bwords

Clen

Dword_dict

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'words' instead of 'word' as the variable name.

Using 'len' as the variable name instead of the function.

We use 'word' as the variable name for each element in words and map it to its length.

5fill in blank

hard

Fill all three blanks to complete the memoization dictionary usage in the word break function.

DSA Python

def word_break_memo(s, word_dict, memo):
    if s in memo:
        return [1]
    for i in range(1, len(s) + 1):
        prefix = s[:i]
        if prefix in word_dict and word_break_memo(s[2], word_dict, memo):
            memo[s] = [3]
            return True
    memo[s] = False
    return False

Drag options to blanks, or click blank then click option'

Amemo[s]

B[i:]

CTrue

DFalse

Attempts:

3 left

💡 Hint

Common Mistakes

Returning memo instead of memo[s].

Using parentheses instead of square brackets for slicing.

Storing False instead of True when segmentation succeeds.

We return memo[s] if s is in memo, slice s[i:] for recursion, and store True when segmentation is possible.

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