• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift与LLVM-Clang原理与示例发布时间:2022-07-13
下一篇:
《Swift开发指南》国内第一本Swift图书上市了发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap