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
}