[Swift]LeetCode139.单词拆分|WordBreak

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, 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

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

说明：

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

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

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

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: 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     // 截取字符串：指定索引和字符数
22     // - begin: 开始截取处索引
23     // - count: 截取的字符数量
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 }