力扣算法——140WordBreakII【H】

class Solution { 2 public: 3 unordered_map<string, vector<string>>map; 4 vector<string> wordBreak(string s, unordered_set<string> &dict) { 5 if (map.find(s) != map.end())return map[s]; 6 if (s.empty())return { "" }; 7 vector<string>res; 8 for (auto word : dict) 9 { 10 if (s.substr(0, word.size()) != word)continue; 11 vector<string>rem = wordBreak(s.substr(word.size()), dict); 12 for (auto str : rem) 13 res.push_back(word + (str.empty() ? "" : " ") + str); 14 } 15 return map[s] = res; 16 } 17 };

 

　　方法二：使用动态规划

 1 //使用动态规划
 2 
 3 class Solution {
 4 public:
 5     vector<string> wordBreak(string s, unordered_set<string> &dict) {
 6         int len = s.length();
 7         dp = new vector<bool>[len];
 8         for (int pos = 0; pos < len; pos++) {
 9             for (int i = 1; i < len - pos + 1; i++) {
10                 if (dict.find(s.substr(pos, i)) != dict.end())
11                     dp[pos].push_back(true);
12                 else
13                     dp[pos].push_back(false);
14             }
15         }
16         dfs(s, len - 1);
17         return res;
18     }
19     void dfs(string s, int n) {
20         if (n >= 0) {
21             for (int i = n; i >= 0; i--) {
22                 if (dp[i][n - i]) {
23                     mid.push_back(s.substr(i, n - i + 1));
24                     dfs(s, i - 1);
25                     mid.pop_back();
26                 }
27             }
28         }
29         else {
30             string r;
31             for (int j = mid.size() - 1; j >= 0; j--) {
32                 r += mid[j];
33                 if (j > 0)
34                     r += " ";
35             }
36             res.push_back(r);
37         }
38     }
39     vector<bool> *dp;
40     vector<string> res;
41     vector<string> mid;
42 };

 

力扣算法——140WordBreakII【H】

标签：red   The   tor   nat   方法   使用   void   lis   NPU