刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/word-break/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

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

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

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

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

思路

这道题如果原始思路的话，应该会是记忆化搜索，不然复杂度就太高了。
“发力富少”一些的话，就是动态规划，但是底层思路是类似的

都是用易得到的结果逐步积累，解出更复杂的问题

• dp数组含义：dp[i] 为 s 中前 i 个字符组成的字符串能否由 wordDict 中的词组合而成
• 状态转移方程：dp[i] = dp[j] && (s[j-1, i] in wordDict)

这里为什么只考虑s[j-1, i]是否属于一个词，那是因为即使有多个词，在后续计算中也一定能够算出来，所以暂时只考虑一个词即可。

• 初始化：dp[0] = true

其实代码基本就出来了，有个小技巧就是将wordDict转成哈希表，便于判断是否可以匹配。上代码

代码

func wordBreak(s string, wordDict []string) bool {
    // 转哈希表，快速校验是否可以匹配
	wordMap := make(map[string]bool)
	for _, w := range wordDict {
		wordMap[w] = true
	}
	dp := make([]bool, len(s) + 1)
    // dp 初始值
	dp[0] = true
    // dp 一步步往后计算
	for i := 1; i <= len(s); i++ {
        // dp 遍历每一个可能的空隙
		for j := 0; j < i; j++ {
            // 状态转移方程
            // dp[i] = dp[j] && (s[j-1, i] in wordDict)
			if dp[j] && wordMap[s[j:i]] {
				dp[i] = true
                // 找到就撤
				break
			}
		}
	}
	return dp[len(s)]
}