Function WordBreak

dynamic/wordbreak.go:10–28

WordBreak checks if the input string can be segmented into words from a dictionary

(s string, wordDict []string)

// WordBreak checks if the input string can be segmented into words from a dictionary
func WordBreak(s string, wordDict []string) bool {
	wordSet := make(map[string]bool)
	for _, word := range wordDict {
		wordSet[word] = true
	}

	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] && wordSet[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}