Article From:https://www.cnblogs.com/strengthen/p/9967645.html

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

```Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because `"leetcode"` can be segmented as `"leet code"`.
```

Example 2:

```Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because `"`applepenapple`"` can be segmented as `"`apple pen apple`"`.
Note that you are allowed to reuse a dictionary word.
```

Example 3:

```Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false```

Given a non-empty strings And a dictionary with a list of non-empty wordswordDict，Judgements Can spaces be split into one or more words that appear in a dictionary?

Explain:

• The words in the dictionary can be reused when splitting.
• You can assume that there are no repetitive words in the dictionary.

Example 1:

`Input: s = Leet code, wordDict = ["leet", "code"]Output: trueInterpretation: Return true because "leetcode" can be split into "leet co"De ".`

Example 2:

```Input: s = Apple pen apple, wordDict = ["apple", "pen"]Output: trueInterpretation: Return true because`"`applepenapple`"` Can be split up`"`apple pen apple`"`。
Note that you can reuse the words in the dictionary.```

Example 3:

`Input: s = catsandog, wordDict = ["cat s", "dog", "s and", "and", "cat"]Output: false`

`20ms`
``` 1 class Solution {
2     func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
3         var dp = Array(repeating:false,count:s.count + 1)
4         var wordSet = Set(wordDict)
5         var maxWordLen = 0
6         for word in wordDict {
7             maxWordLen = max(maxWordLen,word.count)
8         }
9
10         dp[0] = true
11         var s = Array(s)
12         for start in stride(from:0,to:s.count,by:1) {
13             if !dp[start] {
14                 continue
15             }
16             for end in stride(from:start, to:s.count, by:1) {
17                 if end - start + 1 > maxWordLen {
18                     break
19                 }
20                 if dp[start] && wordSet.contains(String(s[start...end])) {
21                     dp[end + 1] = true
22                 }
23             }
24         }
25         return dp[s.count]
26     }
27 }```

28ms

``` 1 class Solution {
2     func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
3         let wordSet = Set(wordDict)
4         var dp = Array(repeating: false, count: s.count + 1), maxLength = 0
5         dp[0] = true
6         for word in wordSet {
7             maxLength = max(maxLength, word.count)
8         }
9         for i in 1...s.count {
10             for j in 0..<i {
11                 if i - j <= maxLength && dp[j] && wordSet.contains(String(s.prefix(i).suffix(i - j))) {
12                     dp[i] = true
13                     break
14                 }
15             }
16         }
17         return dp.last!
18     }
19 }```

36ms

``` 1 class Solution {
2     var memo: [String: Bool] = [:]
3     func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
4         // print("This is s: \(s) and dict : \(wordDict)")
5         if memo[s] != nil && memo[s] == false {
6             return false
7         }
8         if s.isEmpty {
9             return true
10         }
11         for word in wordDict {
12             var newS = s
13             if newS.hasPrefix(word) {
14                 let range = 0...word.count
15                 let replace = ""
16                 newS = String(newS.dropFirst(word.count))
17                 // print("new2 : \(newS)")
18                 if wordBreak(newS, wordDict) {
19                     memo[s] = true
20                     return true
21                 }
22             }
23         }
24         memo[s] = false
25         return false
26     }
27 }```

40ms

``` 1 class Solution {
2     func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
3         var hash = [String:Bool]()
4         var mem = [Int:Bool]()
5         for word in wordDict {
6             hash[word] = true
7         }
8         let chars = Array(s).map { String(\$0) }
9         return helper(chars,0,"",hash,&mem)
10     }
11     func helper(_ chars: [String], _ index: Int, _ curString:String, _ hash:[String:Bool],  _ mem: inout [Int:Bool] ) -> Bool {
12         if index == chars.count { return curString == "" }
13         if curString == "" {
14             if mem[index] == true { return false }
15             else { mem[index] = true }
16         }
17         let newStr = curString + chars[index]
18         if hash[newStr] == true {
19             return helper(chars,index+1,"",hash,&mem) || helper(chars,index+1,newStr,hash,&mem)
20         } else {
21             return helper(chars,index+1,newStr,hash,&mem)
22         }
23     }
24 }```

112ms

``` 1 class Solution {
2     func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
3         let dict = Dictionary(grouping: wordDict, by: { \$0 })
4         var helper = [Int](repeating: -1, count: s.count)
5
6         func wordBreak(_ start: Int) -> Bool {
7             if start == s.count { return true }
8             if helper[start] != -1 { return helper[start] == 1 }
9             for j in start..<s.count {
10                 let str: String = String(s[s.index(s.startIndex, offsetBy: start)...s.index(s.startIndex, offsetBy: j)])
11                 if dict[str] != nil && wordBreak(j+1) {
12                     helper[start] = 1
13                     return true
14                 }
15             }
16             helper[start] = 0
17             return false
18         }
19         return wordBreak(0)
20     }
21 }```

120ms

``` 1 class Solution {
2     func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
3         var wordSet:Set<String> = Set<String>(wordDict)
4         var dp:[Bool] = [Bool](repeating:false,count:s.count + 1)
5         dp[0] = true
6         for i in 0..<dp.count
7         {
8             for j in 0..<i
9             {
10                 if dp[j] && wordSet.contains(s.subString(j, i - j))
11                 {
12                     dp[i] = true
13                     break
14                 }
15             }
16         }
17         return dp.last!
18     }
19 }
20 extension String {
21     // Interception String: Specifies Index and Number of Characters22     // - begin: Beginning Interceptor Index23     // - count: Number of characters intercepted
24     func subString(_ begin:Int,_ count:Int) -> String {
25         let start = self.index(self.startIndex, offsetBy: max(0, begin))
26         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
27         return String(self[start..<end])
28     }
29 }```