用深度优先搜索,注意优化时间复杂度,否则会超时:
优化后
class Solution { public: vector<string> wordBreak(string s, unordered_set<string> &dict) { unordered_map<string, vector<string>> mp; vector<string> res = dfs(dict, s, mp); return res; } vector<string> dfs(unordered_set<string> &dict, string s, unordered_map<string, vector<string> > &mp) { if (s.empty()) return {""}; if (mp.count(s)) return mp[s]; vector<string> res; for (int i = 1; i <= s.size(); ++i) { string word = s.substr(0, i); if (!dict.count(word)) continue; vector<string> coming = dfs(dict, s.substr(i), mp); for (string str : coming) { res.push_back(word + (str.empty() ? "" : " ") + str); } } return mp[s] = res; } };
优化前
class Solution { public: vector<string> wordBreak(string s, unordered_set<string> &dict) { vector<string> res; dfs(dict, s, res, vector<string>()); return res; } void dfs(unordered_set<string> &dict, string s, vector<string> &res, vector<string> words) { if (s.size() < 1) { res.push_back(vec2string(words)); return; } for (int i = 1; i <= s.size(); ++i) { string sub = s.substr(0, i); words.push_back(sub); if (dict.find(sub) != dict.end()) dfs(dict, s.substr(i), res, words); words.pop_back(); } } string vec2string(vector<string> vec) { string s; for (int i = 0; i < vec.size(); ++i) { s += vec[i]; if (i != vec.size() - 1) s += " "; } return s; } };