package main

import (
	"strings"
)

func wordBreak(s string, wordDict []string) []string {
	resMap := make(map[string][]string)
	return wordBreakDFS(s, wordDict, &resMap)
}

func wordBreakDFS(s string, wordDict []string, resMap *map[string][]string) []string {
	if _, ok := (*resMap)[s]; ok { // DFS solution is very pratical! Try to remember
		return (*resMap)[s]
	} // Use a map to limit the search
	if len(s) == 0 {
		return []string{""}
	}
	res := make([]string, 0)
	for i := range wordDict {
		if strings.HasPrefix(s, wordDict[i]) {
			sublist := wordBreakDFS(s[len(wordDict[i]):], wordDict, resMap)
			for j := range sublist {
				var suffix string
				if sublist[j] != "" {
					suffix = " " + sublist[j]
				}
				res = append(res, wordDict[i]+suffix)
			}
		}
	}
	(*resMap)[s] = res
	return res
}

// func main() {
// 	fmt.Println(wordBreak(
// 		"catsanddog",
// 		[]string{"cat", "cats", "and", "sand", "dog"}))
// 	fmt.Println(wordBreak(
// 		"pineapplepenapple",
// 		[]string{"apple", "pen", "applepen", "pine", "pineapple"}))
// 	fmt.Println(wordBreak(
// 		"catsandog",
// 		[]string{"cats", "dog", "sand", "and", "cat"}))
// }