Article From:https://www.cnblogs.com/strengthen/p/9967645.html

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

Given a non-empty strings And a dictionary with a list of non-empty wordswordDict,Judgements Can spaces be split into one or more words that appear in a dictionary?

Explain:

  • The words in the dictionary can be reused when splitting.
  • You can assume that there are no repetitive words in the dictionary.

Example 1:

Input: s = Leet code, wordDict = ["leet", "code"]Output: trueInterpretation: Return true because "leetcode" can be split into "leet co"De ".

Example 2:

Input: s = Apple pen apple, wordDict = ["apple", "pen"]Output: trueInterpretation: Return true because"applepenapple" Can be split up"apple pen apple"。
     Note that you can reuse the words in the dictionary.

Example 3:

Input: s = catsandog, wordDict = ["cat s", "dog", "s and", "and", "cat"]Output: 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     // Interception String: Specifies Index and Number of Characters22     // - begin: Beginning Interceptor Index23     // - count: Number of characters intercepted
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 }

 

Leave a Reply

Your email address will not be published. Required fields are marked *