Word Break

1. Problem Description

Given a non-empty string s and a list wordDict containing non-empty words, determine whether s can be segmented by spaces into one or more words that appear in the dictionary.

2. Approach

• In simple terms, choose N words from the dictionary; if they can match s, return true
• DFS
• DFS + memoization

3. Implementation

3.1. DFS

// DFS
func wordBreak(s string, wordDict []string) bool {
    m := make(map[string]bool, 0)
    for _, word := range wordDict {
        m[word] = true
    }
    return wordBreakDFS(s, 0, m)
}

func wordBreakDFS(s string, index int, m map[string]bool) bool {
    if index == len(s) {
        return true
    }
    for i := index+1; i <= len(s); i++ {
        current := s[index:i]
        if m[current] && wordBreakDFS(s, i, m) {
            return true
        }
    }
    return false
}

3.2. DFS + Memoization

func wordBreak(s string, wordDict []string) bool {
    m := make(map[string]bool, 0)
    for _, word := range wordDict {
        m[word] = true
    }
    memo := make(map[int]bool, 0)
    return wordBreakDFS(s, 0, m, memo)
}

func wordBreakDFS(s string, index int, m map[string]bool, memo map[int]bool) bool {
    if index == len(s) {
        return true
    }
    canBreak, ok := memo[index]
    if ok {
        return canBreak
    }
    canBreak = false
    for i := index+1; i <= len(s); i++ {
        current := s[index:i]
        if m[current] && wordBreakDFS(s, i, m, memo) {// Note: all results need to be enumerated here, so wordBreakDFS cannot be returned directly
            canBreak =  true
        }
    }
    memo[index] = canBreak
    return canBreak
}

4. References

• 139. Word Break - LeetCode