Word Break Problem in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Break Check

What is the output of the following code that checks if the string can be segmented into dictionary words?

DSA Python

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[-1]

s = "applepenapple"
word_dict = {"apple", "pen"}
print(word_break(s, word_dict))

A True

B False

C SyntaxError

D IndexError

💡 Hint

Think about whether the string can be split into the words 'apple' and 'pen'.

The string 'applepenapple' can be segmented as 'apple' + 'pen' + 'apple', all present in the dictionary, so the output is True.

❓ Predict Output

intermediate

Output of Word Break with No Possible Segmentation

What is the output of this code when the string cannot be segmented into dictionary words?

DSA Python

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[-1]

s = "catsandog"
word_dict = {"cats", "dog", "sand", "and", "cat"}
print(word_break(s, word_dict))

A True

B False

C KeyError

D TypeError

💡 Hint

Check if the string can be split into the given dictionary words.

The string 'catsandog' cannot be segmented into the dictionary words because 'og' is not in the dictionary, so the output is False.

🧠 Conceptual

advanced

Understanding the DP Array in Word Break

In the Word Break problem, what does the boolean array dp represent after the algorithm finishes?

A dp[i] is True if the substring s[i:] can be segmented into dictionary words

B dp[i] stores the length of the longest dictionary word ending at i

C dp[i] counts the number of ways to segment s[:i]

D dp[i] is True if the substring s[:i] can be segmented into dictionary words

💡 Hint

Think about what the index i in dp corresponds to in the string.

dp[i] indicates whether the substring from the start up to index i (exclusive) can be segmented into words from the dictionary.

🔧 Debug

advanced

Identify the Error in Word Break Implementation

What error will this code raise when executed?

DSA Python

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

s = "leetcode"
word_dict = {"leet", "code"}
print(word_break(s, word_dict))

A False

B TypeError

C IndexError

D True

💡 Hint

Check the size of dp and the indices used to access it.

The dp array is initialized with length len(s), but the code accesses dp[i] where i can be len(s), causing IndexError.

🚀 Application

expert

Number of Ways to Segment String Using Word Break

Given the string and dictionary below, what is the number of ways to segment the string into dictionary words?

DSA Python

def word_break_count(s, word_dict):
    dp = [0] * (len(s) + 1)
    dp[0] = 1
    for i in range(1, len(s) + 1):
        for j in range(i):
            if s[j:i] in word_dict:
                dp[i] += dp[j]
    return dp[-1]

s = "catsanddog"
word_dict = {"cat", "cats", "and", "sand", "dog"}
print(word_break_count(s, word_dict))

A 2

B 3

C 1

D 0

💡 Hint

Count all possible segmentations like 'cats and dog' and 'cat sand dog'.

There are exactly two ways to segment 'catsanddog': 'cats and dog' and 'cat sand dog'.

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