1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
// @Title: 单词拆分 II (Word Break II)
// @Author: 15816537946@163.com
// @Date: 2019-09-06 23:23:43
// @Runtime: 4 ms
// @Memory: 2.6 MB
/*
 * @lc app=leetcode.cn id=140 lang=golang
 *
 * [140] 单词拆分 II
 *
 * https://leetcode-cn.com/problems/word-break-ii/description/
 *
 * algorithms
 * Hard (37.39%)
 * Likes:    69
 * Dislikes: 0
 * Total Accepted:    5.8K
 * Total Submissions: 15.6K
 * Testcase Example:  '"catsanddog"\n["cat","cats","and","sand","dog"]'
 *
 * 给定一个非空字符串 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 {
	mp := make(map[string]bool)
	for _, v := range wordDict {
		mp[v] = true
	}

	// 1. 动态规划, 判断字符串是否能被拆分
	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] && mp[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}

	// 2. 判断s是否可以被wordDict里的元素分割
	ret := make([]string,0)
	if !dp[len(s)] {
		return ret
	}

	// 3. dfs
	var DFS = func(string, []string) {}
	DFS = func(ns string, r []string) {
		if len(ns) == 0 {
			ret = append(ret, strings.Join(r," "))
			return 
		}
		for i:=1;i<=len(ns);i++ {
			if mp[ns[:i]] {
				DFS(ns[i:],append(r, ns[:i]))
			}
		}
	}
	DFS(s, []string{})
	return ret
}