Solving Word Break Problem in Go: Step-by-Step Guide

Solving the Word Break Problem in Go: A Step-by-Step Guide

The Word Break Problem is one of those classic algorithmic challenges that shows up frequently in coding interviews and real-world text processing applications. At its core, the problem asks a deceptively simple question: given a string and a dictionary of valid words, can the string be segmented into a sequence of one or more dictionary words? In this tutorial, we will walk through the problem from first principles, build up a dynamic programming solution in Go, optimize it, and discuss best practices along the way.

What Is the Word Break Problem?

Formally, the problem is defined as follows. You are given a string s and a list of strings wordDict representing a dictionary of valid words. You must return true if s can be segmented into a space-separated sequence of one or more dictionary words, and false otherwise. Each word in the dictionary may be reused multiple times in the segmentation.

For example, given s = "leetcode" and wordDict = ["leet", "code"], the answer is true because "leetcode" can be split into "leet" and "code". However, given s = "catsandog" and wordDict = ["cats", "dog", "sand", "and", "cat"], the answer is false because no valid segmentation exists that covers the entire string.

Why It Matters

The Word Break Problem is not just an academic exercise. It has direct applications in several domains:

• Natural Language Processing: Tokenizing text without whitespace, such as Chinese text segmentation or hashtag splitting.
• Search Engines: Breaking compound queries or autocomplete suggestions into searchable tokens.
• Spell Checkers: Suggesting valid word boundaries for concatenated or mistyped input.
• URL and Domain Parsing: Detecting meaningful segments in concatenated identifiers.

Beyond its practical uses, the problem is an excellent teaching tool. It demonstrates the power of dynamic programming, the pitfalls of naive recursion, and the importance of choosing the right data structures for lookup performance.

Understanding the Naive Recursive Approach

Before jumping to the optimal solution, it helps to understand why a naive recursive approach fails. The idea is straightforward: at each position in the string, try every possible prefix. If the prefix is in the dictionary, recursively check the remaining suffix. If any recursive call returns true, the entire string is segmentable.

package main

import "fmt"

func wordBreakNaive(s string, wordDict []string) bool {
    dict := make(map[string]bool)
    for _, w := range wordDict {
        dict[w] = true
    }
    return helper(s, dict)
}

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

func main() {
    fmt.Println(wordBreakNaive("leetcode", []string{"leet", "code"}))
}

While this works for short inputs, it has exponential time complexity. The same substrings are recomputed repeatedly across different branches of the recursion tree. For a string of length n, the worst-case number of recursive calls grows as O(2^n), which becomes unusable for strings longer than about 25 characters.

Adding Memoization

The first optimization is to cache results for substrings we have already computed. This technique, called memoization, transforms the exponential recursion into a polynomial algorithm. We store whether each suffix starting at a given index is segmentable, so we never compute the same suffix twice.

package main

import "fmt"

func wordBreakMemo(s string, wordDict []string) bool {
    dict := make(map[string]bool)
    for _, w := range wordDict {
        dict[w] = true
    }
    memo := make(map[int]bool)
    return helperMemo(s, 0, dict, memo)
}

func helperMemo(s string, start int, dict map[string]bool, memo map[int]bool) bool {
    if start == len(s) {
        return true
    }
    if val, ok := memo[start]; ok {
        return val
    }
    for end := start + 1; end <= len(s); end++ {
        prefix := s[start:end]
        if dict[prefix] && helperMemo(s, end, dict, memo) {
            memo[start] = true
            return true
        }
    }
    memo[start] = false
    return false
}

func main() {
    fmt.Println(wordBreakMemo("catsandog", []string{"cats", "dog", "sand", "and", "cat"}))
}

With memoization, the time complexity drops to O(n^2) in the worst case, where n is the length of the string. Each starting index is computed at most once, and for each index we iterate over possible end positions. The space complexity is O(n) for the memoization map plus the recursion stack.

The Bottom-Up Dynamic Programming Solution

While the memoized recursive solution is correct and efficient, many developers prefer an iterative bottom-up dynamic programming approach. This avoids recursion stack overhead and often reads more naturally once you understand the state transitions.

The key insight is to define a boolean array dp where dp[i] indicates whether the substring s[0:i] can be segmented into dictionary words. We initialize dp[0] = true because an empty string is trivially segmentable. Then, for each position i from 1 to n, we check every possible split point j from 0 to i-1. If dp[j] is true and the substring s[j:i] is in the dictionary, then dp[i] becomes true.

package main

import "fmt"

func wordBreak(s string, wordDict []string) bool {
    dict := make(map[string]bool)
    maxLen := 0
    for _, w := range wordDict {
        dict[w] = true
        if len(w) > maxLen {
            maxLen = len(w)
        }
    }

    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true

    for i := 1; i <= n; i++ {
        // Only check j within the maximum word length to avoid unnecessary work
        start := 0
        if i-maxLen > 0 {
            start = i - maxLen
        }
        for j := start; j < i; j++ {
            if dp[j] && dict[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

func main() {
    tests := []struct {
        s        string
        wordDict []string
        expected bool
    }{
        {"leetcode", []string{"leet", "code"}, true},
        {"applepenapple", []string{"apple", "pen"}, true},
        {"catsandog", []string{"cats", "dog", "sand", "and", "cat"}, false},
        {"", []string{"a"}, true},
        {"aaaaaaa", []string{"aaaa", "aaa"}, true},
    }

    for _, t := range tests {
        result := wordBreak(t.s, t.wordDict)
        status := "PASS"
        if result != t.expected {
            status = "FAIL"
        }
        fmt.Printf("%s: wordBreak(%q, %v) = %v (expected %v)\n", status, t.s, t.wordDict, result, t.expected)
    }
}

Notice the optimization involving maxLen. Instead of checking every split point j from 0 to i-1, we only check those within the length of the longest dictionary word. This is because any substring longer than maxLen cannot possibly be in the dictionary. In practice, this optimization dramatically reduces the number of inner loop iterations, especially when the dictionary contains short words and the input string is long.

Tracing Through an Example

Let us trace through the algorithm with s = "leetcode" and wordDict = ["leet", "code"]. The dictionary map is {"leet": true, "code": true} and maxLen = 4. The dp array starts as [true, false, false, false, false, false, false, false, false].

• i=1: Check j=0, substring "l" not in dict. dp[1] stays false.
• i=2: Check j=0,1, substrings "le", "e" not in dict. dp[2] stays false.
• i=3: Similar checks fail. dp[3] stays false.
• i=4: Check j=0, substring "leet" is in dict and dp[0] is true. dp[4] becomes true.
• i=5: Check j=1..4, no valid combination. dp[5] stays false.
• i=6: Check j=2..5, no valid combination. dp[6] stays false.
• i=7: Check j=3..6, no valid combination. dp[7] stays false.
• i=8: Check j=4, substring "code" is in dict and dp[4] is true. dp[8] becomes true.

The final answer is dp[8] = true, which is correct.

Reconstructing the Segmentation

Sometimes knowing that a segmentation exists is not enough. You may want to return the actual word boundaries. To do this, we extend the DP array to store not just a boolean but also the index of the previous split point that led to a valid segmentation. After filling the DP table, we backtrack from the end to reconstruct the word sequence.

package main

import "fmt"

func wordBreakSegment(s string, wordDict []string) []string {
    dict := make(map[string]bool)
    maxLen := 0
    for _, w := range wordDict {
        dict[w] = true
        if len(w) > maxLen {
            maxLen = len(w)
        }
    }

    n := len(s)
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = -1
    }
    dp[0] = 0

    for i := 1; i <= n; i++ {
        start := 0
        if i-maxLen > 0 {
            start = i - maxLen
        }
        for j := start; j < i; j++ {
            if dp[j] != -1 && dict[s[j:i]] {
                dp[i] = j
                break
            }
        }
    }

    if dp[n] == -1 {
        return nil
    }

    // Backtrack to build the word list
    var result []string
    end := n
    for end > 0 {
        start := dp[end]
        result = append([]string{s[start:end]}, result...)
        end = start
    }
    return result
}

func main() {
    words := wordBreakSegment("applepenapple", []string{"apple", "pen"})
    fmt.Println(words) // Output: [apple pen apple]
}

This approach maintains the same O(n^2) time complexity but uses an integer array instead of a boolean array. The backtracking step runs in O(n) time since each iteration moves to a previous split point. The result is a clean list of words that reconstructs the original string.

Handling Edge Cases

A robust implementation must handle several edge cases gracefully. First, an empty string should return true because an empty string is trivially segmentable into zero words. Second, an empty dictionary should return false for any non-empty string, since no words are available to form a segmentation. Third, if the input string contains characters that do not appear in any dictionary word, the algorithm should quickly return false.

func wordBreakRobust(s string, wordDict []string) bool {
    if len(s) == 0 {
        return true
    }
    if len(wordDict) == 0 {
        return false
    }

    dict := make(map[string]bool)
    maxLen := 0
    for _, w := range wordDict {
        dict[w] = true
        if len(w) > maxLen {
            maxLen = len(w)
        }
    }

    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true

    for i := 1; i <= n; i++ {
        start := 0
        if i-maxLen > 0 {
            start = i - maxLen
        }
        for j := start; j < i; j++ {
            if dp[j] && dict[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

Best Practices

When implementing the Word Break Problem in production Go code, keep the following best practices in mind:

• Use a map for dictionary lookups: A map[string]bool provides O(1) average lookup time, which is essential for performance. Avoid scanning the dictionary slice linearly.
• Track the maximum word length: This simple optimization can reduce the inner loop from O(n) to O(maxLen), which is significant when the dictionary words are short relative to the input string.
• Prefer bottom-up DP for large inputs: While memoized recursion is elegant, Go has a relatively small default goroutine stack. Deep recursion on long strings can cause stack overflow issues. The iterative approach avoids this entirely.
• Consider a Trie for large dictionaries: If the dictionary is very large or if you need to perform many lookups, a Trie data structure can be more memory-efficient and allows prefix-based searching without slicing the string repeatedly.
• Benchmark with realistic data: Always test your implementation with inputs that reflect your actual use case. Synthetic benchmarks with random strings may not reveal the performance characteristics you encounter in production.
• Avoid unnecessary string allocations: In Go, string slicing s[j:i] does not allocate new memory because strings are immutable and slices share the underlying byte array. However, storing substrings in maps or returning them does allocate. Be mindful of this in hot paths.

Using a Trie for Dictionary Lookup

For scenarios where the dictionary is large or where you want to avoid repeated string slicing, a Trie offers an elegant alternative. Instead of checking every possible substring against a map, you walk the Trie character by character from each starting position. As soon as you reach a node marked as a word end and the corresponding DP position is reachable, you mark the current position as valid.

package main

import "fmt"

type TrieNode struct {
    children map[byte]*TrieNode
    isWord   bool
}

func newTrieNode() *TrieNode {
    return &TrieNode{children: make(map[byte]*TrieNode)}
}

func buildTrie(wordDict []string) *TrieNode {
    root := newTrieNode()
    for _, word := range wordDict {
        node := root
        for i := 0; i < len(word); i++ {
            ch := word[i]
            if node.children[ch] == nil {
                node.children[ch] = newTrieNode()
            }
            node = node.children[ch]
        }
        node.isWord = true
    }
    return root
}

func wordBreakTrie(s string, wordDict []string) bool {
    root := buildTrie(wordDict)
    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true

    for i := 0; i < n; i++ {
        if !dp[i] {
            continue
        }
        node := root
        for j := i; j < n; j++ {
            ch := s[j]
            if node.children[ch] == nil {
                break
            }
            node = node.children[ch]
            if node.isWord {
                dp[j+1] = true
            }
        }
    }
    return dp[n]
}

func main() {
    fmt.Println(wordBreakTrie("leetcode", []string{"leet", "code"}))
    fmt.Println(wordBreakTrie("catsandog", []string{"cats", "dog", "sand", "and", "cat"}))
}

The Trie-based approach has the same theoretical worst-case complexity of O(n^2), but in practice it often performs better because it stops early as soon as a character does not match any Trie path. It also avoids creating substring copies entirely, which reduces garbage collection pressure in Go.

Conclusion

The Word Break Problem is a fantastic example of how dynamic programming transforms an exponential brute-force approach into an efficient polynomial solution. In Go, the bottom-up DP approach with a map-based dictionary and a maximum word length optimization provides an excellent balance of clarity, performance, and memory efficiency. For more demanding use cases involving large dictionaries or repeated lookups, a Trie-based implementation offers additional speedups by avoiding string allocations and enabling early termination. By understanding the trade-offs between memoized recursion, bottom-up DP, and Trie-based solutions, you can choose the right approach for your specific application and write robust, performant code that handles text segmentation with confidence.