力扣算法——140WordBreakII【H】

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:

[]

Solution:
　　方法一，使用递归：【通不过牛客的例子】

 class Solution {

 public:

     unordered_map<string, vector<string>>map;

     vector<string> wordBreak(string s, unordered_set<string> &dict) {

         if (map.find(s) != map.end())return map[s];

         if (s.empty())return { "" };

         vector<string>res;

         for (auto word : dict)

         {

             if (s.substr(, word.size()) != word)continue;

             vector<string>rem = wordBreak(s.substr(word.size()), dict);

             for (auto str : rem)

                 res.push_back(word + (str.empty() ? "" : " ") + str);

         }

         return map[s] = res;

     }

 };


　　方法二：使用动态规划

 //使用动态规划

 class Solution {

 public:

     vector<string> wordBreak(string s, unordered_set<string> &dict) {

         int len = s.length();

         dp = new vector<bool>[len];

         for (int pos = ; pos < len; pos++) {

             for (int i = ; i < len - pos + ; i++) {

                 if (dict.find(s.substr(pos, i)) != dict.end())

                     dp[pos].push_back(true);

                 else

                     dp[pos].push_back(false);

             }

         }

         dfs(s, len - );

         return res;

     }

     void dfs(string s, int n) {

         if (n >= ) {

             for (int i = n; i >= ; i--) {

                 if (dp[i][n - i]) {

                     mid.push_back(s.substr(i, n - i + ));

                     dfs(s, i - );

                     mid.pop_back();

                 }

             }

         }

         else {

             string r;

             for (int j = mid.size() - ; j >= ; j--) {

                 r += mid[j];

                 if (j > )

                     r += " ";

             }

             res.push_back(r);

         }

     }

     vector<bool> *dp;

     vector<string> res;

     vector<string> mid;

 };

巴特西

力扣算法——140WordBreakII【H】

最新文章

热门文章