unordered_set<string> ws;
bool dfs(string &s, int i, string tmp) {
if (m[i] == 0) return m[i];
for (int j = min((int)s.size(), i + maxLen); j > i; --j) {
auto sub = s.substr(i, j - i);
if (ws.count(sub) && dfs(s, j, tmp.size() ? tmp + " " + sub : sub)) m[i] = 1;
vector<string> wordBreak(string s, vector<string>& dict) {
ws = { dict.begin(), dict.end() };
for (auto &w : dict) maxLen = max(maxLen, (int)w.size());
m.assign(s.size(), -1); // -1 = unvisited, 0 = can not reach end, 1 = can reach end.