package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @param dic string字符串一维数组
 * @return bool布尔型
 */
func wordDiv(s string, dic []string) bool {
	//前缀树+动态规划
	trie := &PreTreeNode{0, 0, map[byte]*PreTreeNode{}}
	for i := 0; i < len(dic); i++ {
		trie.Add(dic[i])
	}

	n := len(s)
	dp := make([]bool, n+1)
	dp[n] = true
	for i := n - 1; i >= 0; i-- {
		cur := trie
		for j := i; j < n; j++ {
			c := s[j]
			tmp, ok := cur.nexts[c]
			if !ok {
				break
			}
			cur = tmp

			if tmp.End > 0 {
				dp[i] = dp[i] || dp[j+1]
			}
		}
	}

	return dp[0]
}

type PreTreeNode struct {
	Pass int
	End  int

	nexts map[byte]*PreTreeNode
}

func (node *PreTreeNode) Add(word string) {
	if len(word) == 0 {
		return
	}

	cur := node
	cur.Pass++

	for i := 0; i < len(word); i++ {
		c := word[i]

		_, ok := cur.nexts[c]
		if !ok {
			cur.nexts[c] = &PreTreeNode{0, 0, map[byte]*PreTreeNode{}}
		}

		cur = cur.nexts[c]
		cur.Pass++
	}

	cur.End++

}