单词拆分

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 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

题解：

​ 动态规划问题，分割问题为有重叠的子问题，判断 s 能否能被 wordDict 的子串所表示 等价于 s - wordDict[i] + wordDict[i] ，当字符串减去匹配的子串，剩下的字符串能否被匹配

​ 这里主要有个处理方法比较难想，如何处理字符串的匹配问题，可以放到哈希里面直接切割子串判断

​ 因此我们可以之间从前往后依次判断字符串能否被子串分割，（这里有个小问题，写代码的时候有在考虑时间复杂度的优化，我记录了每次匹配到的子串的位置，这样下次匹配就可以从这个位置向后匹配了，可以减少前面已经匹配的子串，但是败在了 “aaaaaaa” [“aaaa”,“aaa”] 这个样例，这种优化的思路会把字符串分割为 “aaa”， “aaa” ，“a” 导致输出的是 false）

​ 下面的 dp[i] 表示 从起点到第 i 个字母的子串能否被分割，dp[j] && word[s[j:i]] 用来判断 子串是否匹配 以及 避免子串重叠的情况（s[j:i]] 是左闭右开）

func wordBreak(s string, wordDict []string) bool {
    word := make(map[string]bool)
    for _,w := range wordDict {
        word[w] = true
    }
    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] && word[s[j:i]] {
                dp[i] = true
                break
            }
        }
    } 
    return dp[len(s)]
}