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

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:
[]

Given a non-empty strings And a dictionary with a list of non-empty wordswordDict,Add spaces to the string to construct a sentence so that all the words in the sentence are in the dictionary. Return all these possible sentences.

Explain:

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

Example 1:

Input:S = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:[
  "cats and dog",
  "cat sand dog"
]

Example 2:

Input:S = pineapple enappleWordDict = ["apple", "pen", "apple pen", "pine", "pine apple"]Output:["Pine Apple pen apple","Pineapple pen apple""Pine applepen apple"]Explanation: Note that you can reuse words in the dictionary。

Example 3:

Input:S = catsandogWordDict = ["cats", "dog", "sand", "and", "cat"]Output:[]

Beyond the time limit

 1 class Solution {
 2     var m:[String:[String]] = [String:[String]]()
 3     func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
 4         if m[s] != nil {return m[s]!}
 5         if s.isEmpty {return [""]}
 6         var res:[String] = [String]()
 7         for word in wordDict
 8         {
 9             if s.subString(0, word.count) != word {continue}
10             var rem:[String] =  wordBreak(s.subString(word.count), wordDict)
11             for str in rem
12             {
13                  res.append(word + (str.isEmpty ? "" : " ") + str)
14             }
15         }
16         //m[s] = res
17         return res
18     }
19 }
20 
21 extension String {
22     // Interception strings: from index to end23     // - Parameter index: Start index24     // - Returns: Substring
25     func subString(_ index: Int) -> String {
26         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
27         return String(self[theIndex..<endIndex])
28     }
29     
30     // Interception String: Specifies Index and Number of Characters31     // - begin: Beginning Interceptor Index32     // - count: Number of characters intercepted
33     func subString(_ begin:Int,_ count:Int) -> String {
34         let start = self.index(self.startIndex, offsetBy: max(0, begin))
35         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
36         return String(self[start..<end]) 
37     }
38 }

 

Leave a Reply

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