139. 单词拆分

mid

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

1
2
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true

示例 2：

1
2
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

DP

dp[j] = dp[i] && s[i:j] 在不在 wordDict 中

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func wordBreak(s string, wordDict []string) bool {
	dp := make([]bool, len(s)+1)
	dp[0] = true

	wordMap := make(map[string]bool)
	for _, w := range wordDict {
		wordMap[w] = true
	}

	for j := 1; j <= len(s); j++ {
		for i := 0; i < j; i++ {
			if dp[i] && wordMap[s[i:j]] {
				dp[j] = true
				break
			}
		}
	}

	return dp[len(s)]
}

DFS

普通的 dfs 会超时，所以需要记录重复的递归结果

 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
func wordBreak(s string, wordDict []string) bool {
	wordMap := make(map[string]bool)
	for _, w := range wordDict {
		wordMap[w] = true
	}

	dfsMap := make(map[string]bool)

	var dfs func(leftS string) bool
	dfs = func(leftS string) bool {
		if r, ok := dfsMap[leftS]; ok {
			return r
		}
		if leftS == "" {
			return true
		}
		res := false
		for i := 1; i <= len(leftS); i++ {
			if wordMap[leftS[:i]] {
				res = dfs(leftS[i:]) || res
			}
		}
		dfsMap[leftS] = res // 记录重复递归的结果
		return res
	}

	return dfs(s)
}