[Swift]LeetCode140. 单词拆分 II | Word Break II
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
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 = "catsanddog" wordDict =["cat", "cats", "and", "sand", "dog"]Output:[ "cats and dog", "cat sand dog" ]
Example 2:
Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
- 分隔时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
输入: s = "catsanddog" wordDict =["cat", "cats", "and", "sand", "dog"]输出:[ "cats and dog", "cat sand dog" ]
示例 2：
输入: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] 输出: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] 解释: 注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: []
36ms
1 class Solution {
2 func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
3 if s.isEmpty || wordDict.isEmpty {
4 return []
5 }
6
7 let cs = Set(wordDict.map{$0.count})
8 var carr = [Int]()
9 for count in cs {
10 carr.append(count)
11 }
12 let wordSet = Set(wordDict)
13 var res = [String]()
14
15 var subCounts : [[Int]?] = Array(repeating: nil, count: s.count + 1)
16 subCounts[0] = [Int]()
17
18 for i in 0..<s.count where subCounts[i] != nil {
19 for j in 0..<carr.count {
20 if i + carr[j] <= s.count && wordSet.contains((s as NSString).substring(with: NSRange(location: i, length: carr[j]))) {
21 subCounts[i]?.append(carr[j])
22 if subCounts[i + carr[j]] == nil {
23 subCounts[i + carr[j]] = [Int]()
24 }
25 }
26 }
27 }
28
29 if subCounts[s.count] == nil {
30 return []
31 }
32
33 var words = [String]()
34
35 dfs(s, subCounts, 0, &words, &res)
36
37 return res
38 }
39
40 func dfs(_ s : String , _ subLengths : [[Int]?] , _ from : Int, _ words : inout [String], _ res : inout [String]) {
41
42 if s.count == from {
43 let ser = words.joined(separator: " ")
44 res.append(ser)
45 return
46 }
47
48 let tar = subLengths[from]!
49
50 for length in tar {
51 words.append((s as NSString).substring(with: NSRange(location: from, length: length)))
52 dfs(s, subLengths, from + length, &words, &res)
53 words.removeLast()
54 }
55
56 }
57 }40ms
1 class Solution {
2 func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
3
4 var map = [String: [String]]()
5 var wordDict = wordDict
6 return helper(s, &wordDict, &map)
7 }
8 func helper(_ s: String, _ wordDict: inout [String], _ map: inout [String: [String]]) -> [String] {
9 if s.count == 0 { return [""] }
10 if let value = map[s] {
11 return value
12 }
13 var res = [String]()
14 for word in wordDict {
15 if !s.hasPrefix(word) { continue }
16 let subs = helper(s.substring(from: word.endIndex), &wordDict, &map)
17 for sub in subs {
18 if sub.isEmpty {
19 res.append(word)
20 }
21 else {
22 res.append(word + " " + sub)
23 }
24 }
25 }
26 map[s] = res
27 return res
28 }
29 }68ms
1 class Solution {
2 func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
3 var computedSentences = [String: [String]]()
4 return sentences(s, wordDict, &computedSentences)
5 }
6
7 func sentences(_ s: String, _ wordDict: [String], _ computedSentences: inout [String: [String]]) -> [String] {
8
9 if let precomputed = computedSentences[s] {
10 return precomputed
11 }
12
13 if s.isEmpty {
14 return [""]
15 }
16
17 var results = [String]()
18 for word in wordDict where s.starts(with: word) {
19 let subSentences = sentences(String(s.dropFirst(word.count)), wordDict, &computedSentences)
20 for subSentence in subSentences {
21 if subSentence.isEmpty {
22 results.append(word)
23 } else {
24 results.append("\(word) \(subSentence)")
25 }
26 }
27 }
28
29 computedSentences[s] = results
30 return results
31 }
32 }88ms
1 class Solution {
2 var word_set: Set<String> = []
3 var cache: [String: [String]] = [:]
4
5 func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
6 guard s.count > 0 else {
7 return []
8 }
9 word_set = Set<String>(wordDict)
10 return self.word_Break(s)
11 }
12
13 func word_Break(_ s: String) -> [String] {
14 guard s.count > 0 else {
15 return [""]
16 }
17
18 if let answer = cache[s] {
19 return answer
20 }
21
22 var answers:[String] = []
23 for i in 0..<s.count {
24 let index = s.index(s.startIndex, offsetBy: i)
25 let mySubstring = s[...index]
26
27 if word_set.contains(String(mySubstring)) {
28 let nextIndex = s.index(index, offsetBy: 1)
29 let subReturn = word_Break(String(s[nextIndex...]))
30 let fullReturn = subReturn.map(){ partialPath -> String in
31 if partialPath == "" {
32 return "\(mySubstring)"
33 }
34 return "\(mySubstring) \(partialPath)"
35 }
36
37 answers += fullReturn
38 }
39 }
40
41 cache[s] = answers
42 return answers
43 }
44 }