leetcode

0 class Solution {

1 unordered_set<string> us[10];

2

3 vector<string> rec(const string &s, const int start = 0) {

4 const int n = size(s);

5 vector<string> res;

6 string crnt;

7

8 if (start == n) return {""};

9 for (int i = start; i < min(start + 10, n); i++) {

10 crnt += s[i];

11 if (!us[i - start].count(crnt)) continue;

12 for (const auto &s : rec(s, i + 1)) {

13 res.push_back(start == 0 ? "" : " ");

14 res.back() += crnt + s;

15 }

16 }

17

18 return res;

19 }

20

21 public:

22 vector<string> wordBreak(const string &s, const vector<string> &wordDict) {

23 for (const auto &word : wordDict)

24 us[size(word) - 1].insert(word);

25 return rec(s);

26 }

27 };