leetcode 140. 单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入:s = "catsanddog"wordDict = ["cat", "cats", "and", "sand", "dog"]输出:[ "cats and dog", "cat sand dog"]示例 2：
输入:s = "pineapplepenapple"wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]输出:[ "pine apple pen apple", "pineapple pen apple", "pine applepen apple"]解释: 注意你可以重复使用字典中的单词。示例 3：
输入:s = "catsandog"wordDict = ["cats", "dog", "sand", "and", "cat"]输出:[]这道题是上一题的升级版，既然需要返回所有结果，那么回溯基本上跑不了了。不过这道题不能强行回溯，会超时的，需要用到上一题的动态规划先判断字符串能不能被拆分，如果可以再进行回溯。
码到成功：
func wordBreak(s string, wordDict []string) []string { wMap := make(map[string]bool,len(wordDict)) for _,v := range wordDict { wMap[v] = true } //先通过DP判断字符串是否能被拆分 dp := make([]bool, len(s)+1) dp[0] = true for i:=1;i<=len(s);i++ { for j:=0;j<i;j++ { if dp[j] && wMap[s[j:i]] { dp[i] = true break } } } re := []string{} if !dp[len(s)] { return re } //回溯走起 var DFS = func (string,[]string) {} DFS = func(ns string,r []string) { if len(ns) == 0 { re = append(re, strings.Join(r," ")) return } for i:=1; i<=len(ns); i++ { if wMap[ns[:i]] { DFS(ns[i:],append(r,ns[:i])) } } } DFS(s,[]string{}) return re}话不多说，继续努力！
算法梦想家，来跟我一起玩算法，玩音乐，聊聊文学创作，咱们一起天马行空！