word-break.go

// https://leetcode.com/problems/word-break

func wordBreak(s string, wordDict []string) bool {
    wordMap := make(map[string]struct{}, len(wordDict))
    
    for _, word := range wordDict {
        wordMap[word] = struct{}{}
    }
    
    chars := []rune(s)
    n := len(chars)
    dp := make([]int, n + 1)
    
    dp[0] = 1
    
    for i := 0; i < n && dp[n] == 0; i++ {
        if dp[i] == 0 {
            continue
        }
        
        for _, word := range wordDict {
            j := len(word)
            
            if i + j > n {
                continue
            }

            candidate := string(chars[i:i + j])
            
            if _, ok := wordMap[candidate]; ok {
                dp[i + j] = 1
            }
        }
    }
    
    return dp[n] == 1
}