package main

func wordBreakOld(s string, wordDict []string) bool { // TLE :^<
	length := len(s)
	if length == 0 || len(wordDict) == 0 {
		return false
	}
	set := make(map[string]bool, 0)
	min, max := length, 0
	for _, v := range wordDict {
		vLen := len(v)
		if vLen < min {
			min = vLen
		}
		if vLen > max {
			max = vLen
		}
		set[v] = true
	}
	return breakHelper(s, &set, 0, length, min, max)
}

func breakHelper(s string, set *map[string]bool, beg, end, min, max int) bool {
	if beg == end {
		return true
	}
	i := beg + max
	if i > end {
		i = end
	}
	for ; i > beg; i-- {
		if (*set)[s[beg:i]] {
			if breakHelper(s, set, i, end, min, max) {
				return true
			}
		}
	}
	return false
}

func wordBreak(s string, wordDict []string) bool { // Faster DP solution
	length := len(s)
	result := make([]bool, length+1)
	result[0] = true
	set := make(map[string]bool, 0)
	for _, v := range wordDict {
		set[v] = true
	}
	for i := 1; i <= length; i++ {
		for j := 0; j < i; j++ {
			if result[j] && set[s[j:i]] {
				result[i] = true
				break
			}
		}
	}
	return result[length]
}

// func main() {
// 	println(wordBreak(
// 		"catsanddogsand",
// 		[]string{"cats", "and", "sand", "dogs", "dog"}))
// }