Word Break Problem in DSA Go - Time & Space Complexity

Time Complexity: Word Break Problem

O(n^2 * m * k)

Understanding Time Complexity

We want to know 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.

func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s)+1)
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && contains(wordDict, s[j:i]) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}

func contains(dict []string, word string) bool {
    for _, w := range dict {
        if w == word {
            return true
        }
    }
    return false
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over the string length and checking substring membership in the dictionary.
• How many times: Outer loop runs n times, inner loop runs up to n times, and dictionary search runs up to m times per substring.

How Execution Grows With Input

As the string length n grows, the number of substring checks grows roughly with n squared, and each check searches the dictionary of size m.

Input Size (n)	Approx. Operations
10	About 10*10*m = 100*m
100	About 100*100*m = 10,000*m
1000	About 1000*1000*m = 1,000,000*m

Pattern observation: Operations grow roughly with the square of the string length times the dictionary size.

Final Time Complexity

Time Complexity: O(n^2 * m * k)

This means the time grows roughly with the square of the string length, multiplied by the number of dictionary words and average word length.

Common Mistake

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

[OK] Correct: The nested loops and dictionary checks cause the time to grow much faster than linear as the string gets longer.

Interview Connect

Understanding this complexity helps you explain how dynamic programming solves problems efficiently and why dictionary lookup methods matter.

Self-Check

"What if we used a hash set for the dictionary instead of a list? How would the time complexity change?"

Practice

1. What does the Word Break Problem ask you to determine about a given string s and a dictionary of words wordDict?

easy

A. If s can be segmented into a space-separated sequence of one or more dictionary words

B. If s contains any substring from wordDict

C. If s is exactly equal to any word in wordDict

D. If s can be reversed to form a word in wordDict

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks if the entire string s can be split into valid words from the dictionary without leftover characters.

2. Step 2: Differentiate from similar concepts

   It is not enough for s to contain a substring or be equal to a dictionary word; the whole string must be fully segmented.

3. Final Answer:

   If s can be segmented into a sequence of dictionary words -> Option A

4. Quick Check:

   Word Break = Full segmentation check [OK]

Hint: Check if full string splits into dictionary words [OK]

Common Mistakes:

• Thinking partial substring match is enough
• Confusing equality with segmentation
• Ignoring leftover characters after segmentation

2. Which of the following Go function signatures correctly represents a function to solve the Word Break Problem?

easy

A. func wordBreak(wordDict []string, s string) string

B. func wordBreak(s string, wordDict []string) bool

C. func wordBreak(s []string, wordDict string) int

D. func wordBreak(s string, wordDict map[string]int) []string

Solution

1. Step 1: Identify correct parameter types

   The input string s should be a string, and the dictionary wordDict should be a slice of strings.

2. Step 2: Identify correct return type

   The function returns a boolean indicating if segmentation is possible.

3. Final Answer:

   func wordBreak(s string, wordDict []string) bool -> Option B

4. Quick Check:

   Input: string + []string, Output: bool [OK]

Hint: Input string and word list, output bool [OK]

Common Mistakes:

• Swapping parameter types
• Returning wrong data type
• Using map instead of slice without reason

3. What is the output of the following Go code snippet?

func main() {
    s := "leetcode"
    wordDict := []string{"leet", "code"}
    fmt.Println(wordBreak(s, wordDict))
}

func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s)+1)
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && contains(wordDict, s[j:i]) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}

func contains(dict []string, word string) bool {
    for _, w := range dict {
        if w == word {
            return true
        }
    }
    return false
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Understand the dynamic programming approach

   The code uses a boolean slice dp where dp[i] is true if s[:i] can be segmented into dictionary words.

2. Step 2: Trace the example string "leetcode"

   "leet" and "code" are in the dictionary, so dp[len(s)] becomes true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   DP segmentation = true [OK]

Hint: Check dp array for full string length [OK]

Common Mistakes:

• Forgetting to break inner loop after true
• Incorrect substring slicing
• Not initializing dp[0] to true

4. Identify the bug in this Go code for the Word Break Problem:

func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s))
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && contains(wordDict, s[j:i]) {
                dp[i] = true
                break
            }
        }
    }
    return dp[len(s)]
}

medium

A. contains function is missing

B. dp slice length is correct but dp[0] should be false

C. dp slice length should be len(s)+1 and dp[0] initialization is correct

D. Loop indices i and j are reversed

Solution

1. Step 1: Check dp slice size and initialization

   The dp slice must be of size len(s)+1 to include empty substring at index 0, and dp[0] should be true.

2. Step 2: Verify loop bounds and dp usage

   Loops use indices up to len(s), so dp must have length len(s)+1 to avoid index out of range.

3. Final Answer:

   dp slice length should be len(s)+1 and dp[0] initialization is correct -> Option C

4. Quick Check:

   dp size = len(s)+1 [OK]

Hint: dp length = string length + 1 [OK]

Common Mistakes:

• Using dp length as len(s) causes index errors
• Not initializing dp[0] to true
• Incorrect loop ranges causing panic

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which of the following modifications to the Word Break algorithm will correctly handle repeated words without extra space complexity?

hard

A. Replace dp array with a single boolean variable updated each iteration

B. Use a queue to store all possible segmentations and check each fully

C. Sort the dictionary and use binary search for substring checks

D. Use a memoization map to store results of substring checks to avoid recomputation

Solution

1. Step 1: Understand repeated word handling

   Repeated words cause repeated substring checks; memoization stores results to avoid recomputation.

2. Step 2: Analyze options for efficiency

   Memoization reduces time without increasing space beyond needed; queue or sorting do not directly optimize repeated checks; single boolean loses needed state.

3. Final Answer:

   Use a memoization map to store results of substring checks to avoid recomputation -> Option D

4. Quick Check:

   Memoization = efficient repeated checks [OK]

Hint: Memoize substring results to avoid repeated work [OK]

Common Mistakes:

• Ignoring repeated substring computations
• Using single boolean loses segmentation info
• Assuming sorting dictionary helps substring checks