Leetcode 140 Solution

This article provides solution to leetcode question 140 (word-break-ii)

https://leetcode.com/problems/word-break-ii

Solution

class Solution { vector<vector<string>> cache; vector<bool> cached; vector<string> res; public: vector<string> wordBreak(const string& s, int i, unordered_set<string>& wordSet) { vector<string> res;
if (i == s.size()) { res.push_back(""); return res; }
if (cached[i]) return cache[i];
for (int j = i; j < s.size(); j++) { string substr = s.substr(i, j - i + 1);
if (wordSet.find(substr) == wordSet.end()) continue;
auto rest_strs = wordBreak(s, j + 1, wordSet);
for (auto rest_str : rest_strs) res.push_back(rest_str.empty() ? substr : substr + " " + rest_str); }
cached[i] = true; return cache[i] = res; }
vector<string> wordBreak(string s, vector<string>& wordDict) { cache.resize(s.size()); cached.resize(s.size());
unordered_set<string> wordSet;
for (auto word : wordDict) wordSet.insert(word);
return wordBreak(s, 0, wordSet); } };