Word Break Problem in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the input string is empty.

DSA Go

if len(s) == [1] {
    return true
}

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

A0

B1

C-1

Dlen(s)

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 to check for empty string.

Comparing len(s) to -1 which is invalid.

An empty string has length 0, so we check if len(s) == 0.

2fill in blank

medium

Complete the code to iterate over the string indices for substring checks.

DSA Go

for i := 1; i <= [1]; i++ {
    // check substring
}

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

Alen(s) + 1

Blen(s) - 1

Clen(s)

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(s) - 1 which misses the last substring.

Using len(s) + 1 which causes out of range error.

We iterate from 1 to len(s) inclusive to cover all substring lengths.

3fill in blank

hard

Fix the error in the substring extraction to get s[0:i].

DSA Go

prefix := s[[1]:i]

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

Alen(s)

B1

Ci

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 as start index which skips the first character.

Using i as start index which results in empty or wrong substring.

To get the prefix substring from start to i, slice from 0 to i.

4fill in blank

hard

Fill both blanks to check if prefix is in wordDict and suffix can be segmented.

DSA Go

if wordDict[[1]] && dp[[2]] {
    dp[i] = true
}

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

Aprefix

Bsuffix

Ci

Di - len(prefix)

Attempts:

3 left

💡 Hint

Common Mistakes

Using suffix instead of prefix for dictionary check.

Using i instead of i - len(prefix) for dp index.

We check if prefix is in wordDict and dp at index i - len(prefix) is true.

5fill in blank

hard

Fill all three blanks to complete the word break function using dynamic programming.

DSA Go

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

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

Alen(s)

Blen(s) - 1

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(s) - 1 causing incomplete checks.

Returning dp[0] which only represents empty string.

dp array size and loop limits use len(s), and we return dp[len(s)] for full string segmentation.

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