[Swift]LeetCode139. 单词拆分 | Word Break
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（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, 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 }- 上一篇 »小程序 css 文字溢出，长度过长用 。。。
- 下一篇 »css 换行 且不分割最后一个单词