[Swift]LeetCode140.单词拆分II|WordBreakII

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 }