Word Break Problem in DSA Python - Time & Space Complexity

Time Complexity: Word Break Problem

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to solve the Word Break Problem changes as the input grows.

Specifically, how does checking if a string can be split into dictionary words scale with string length?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

wordDict = set(["apple", "pen", "applepen", "pine", "pineapple"])

s = "pineapplepenapple"

# dp[i] means s[:i] can be segmented

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

print(dp[len(s)])
    

This code checks if the string can be split into words from the dictionary using dynamic programming.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where for each position i, we check all positions j before i.
• How many times: Outer loop runs n times, inner loop runs up to n times, so roughly n x n checks.

How Execution Grows With Input

As the string length grows, the number of checks grows roughly with the square of the length.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: Doubling the input length roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n^3)

This means the time grows roughly with the cube of the string length due to substring checks.

Common Mistake

[X] Wrong: "The solution runs in linear time because it just loops through the string once."

[OK] Correct: The code has nested loops, so it checks many substrings, not just once through the string.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves over naive recursion and why nested loops matter.

Self-Check

"What if we used a trie data structure for the dictionary lookups? How would the time complexity change?"

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