139. 单词拆分

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

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

• 时间复杂度：O(n^2) ，其中 n 为字符串 s 的长度。我们一共有 O(n) 个状态需要计算，每次计算需要枚举 O(n) 个分割点，哈希表判断一个字符串是否出现在给定的字符串列表需要 O(1) 的时间，因此总时间复杂度为 O(n^2)。
  

• 空间复杂度：O(n) ，其中 n 为字符串 s 的长度。我们需要 O(n) 的空间存放 dp 值以及哈希表亦需要 O(n) 的空间复杂度，因此总空间复杂度为 O(n)。
  ```go //dp,完全背包🎒，时间On^2，空间On func wordBreak(s string, wordDict []string) bool { n := len(s) wordMap := make(map[string]bool)

  for _, w := range wordDict { //1，初次遍历，类型建哈希表

    wordMap[w] = true

  }

  dp := make([]bool, n+1) dp[0] = true

  for i := 1; i <= n; i++ {

    for j := 0; j < i; j++ {
        if dp[j] && wordMap[s[j:i]] {       //前0-j; j-i 两种
            dp[i] = true                    //如果在第j个分层就找到了，结束循环，判断✅
            break
        }
    }
  

  } return dp[n] }

```

如果一个字符串s可以由wordDict组成。
那么如果给s后面增加一个字符c，如何判断新的s + c是否还能由wordDict组成呢？

只要判断原来的s是否可以切成两个子字符串s1和s2，且
1）s1可以由wordDict组成
2）s2 + c就是wordDict里面某个单词