140. Word Break II
给一个string :s和一组string array : wordDict
在s中加入空格，让s中的单字都在wordDict里
并回传所有可能的组合
思路:
其实跟Word Break I差不多就只是多了要记录组合而已
首先先把wordDict里的单字依照字母分类
用DFS从s的字首开始，去找WordDict中对应的字母分类
比对成功后把s扣掉比对成功的单字，继续找下去
一直到s比对完，就可以记录了
golang code:
func wordBreak(s string, wordDict []string) []string {
rec := make([][]int, 26)
n := len(s)
for key, val := range wordDict {
rec[val[0]-'a'] = append(rec[val[0]-'a'], key)
}
res := []string{}
var dfs func(idx int, mem []int)
dfs = func(idx int, mem []int) {
if idx == n {
tmp := strings.Builder{}
tmp.WriteString(wordDict[mem[0]])
for _, val := range mem[1:] {
tmp.WriteString(" ")
tmp.WriteString(wordDict[val])
}
res = append(res, tmp.String())
return
}
for _, key := range rec[s[idx]-'a'] {
val := wordDict[key]
l := len(val)
if idx+l <= n && s[idx:idx+l] == val {
mem = append(mem, key)
dfs(idx+l, mem)
mem = mem[:len(mem)-1]
}
}
}
dfs(0, []int{})
return res
}