Word Break Problem in DSA Go - Build from Scratch

Word Break Problem

📖 Scenario: Imagine you have a long string of letters without spaces, like a secret message. You want to check if this message can be split into valid words from a dictionary you have.

🎯 Goal: You will build a program that checks if a given string can be broken into a sequence of dictionary words.

📋 What You'll Learn

Create a string variable with the exact value 'applepenapple'

Create a slice of strings called dictionary with the exact words 'apple' and 'pen'

Write a function canBreak that returns true if the string can be segmented into dictionary words

Print the result of canBreak when called with the string and dictionary

💡 Why This Matters

🌍 Real World

This problem is useful in text processing, such as checking if a sentence can be formed from known words, or in natural language processing tasks.

💼 Career

Understanding recursive problem solving and string manipulation is important for software developers working on search engines, spell checkers, and language-based applications.

1

Create the input string and dictionary

Create a string variable called input with the value "applepenapple". Then create a slice of strings called dictionary with the exact words "apple" and "pen".

DSA Go

# Your code here

Hint

Use input := "applepenapple" to create the string and dictionary := []string{"apple", "pen"} for the list of words.

2

Create a helper function to check word presence

Create a function called isInDictionary that takes a string word and a slice of strings dictionary. It should return true if word is in dictionary, otherwise false.

DSA Go

package main

func main() {
    input := "applepenapple"
    dictionary := []string{"apple", "pen"}
}

// Your code here

Hint

Use a for loop to check each word in dictionary. Return true if you find word, else false.

3

Implement the word break logic

Create a function called canBreak that takes a string s and a slice of strings dictionary. It should return true if s can be segmented into a sequence of dictionary words. Use recursion and the isInDictionary function.

DSA Go

package main

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

// Your code here

func main() {
    input := "applepenapple"
    dictionary := []string{"apple", "pen"}
}

Hint

Try all prefixes of s. If a prefix is in the dictionary and the rest of the string can be broken, return true. Otherwise, return false.

4

Print the result of the word break check

Add a print statement in main to display the result of calling canBreak with input and dictionary.

DSA Go

package main

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

func canBreak(s string, dictionary []string) bool {
    if len(s) == 0 {
        return true
    }
    for i := 1; i <= len(s); i++ {
        prefix := s[:i]
        if isInDictionary(prefix, dictionary) && canBreak(s[i:], dictionary) {
            return true
        }
    }
    return false
}

func main() {
    input := "applepenapple"
    dictionary := []string{"apple", "pen"}
    // Your code here
}

Hint

Use fmt.Println(canBreak(input, dictionary)) to print the result.

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