leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0140.cpp (777B)

      1 class Solution {
      2     unordered_set<string> us[10];
      3 
      4     vector<string> rec(const string &s, const int start = 0) {
      5         const int n = size(s);
      6         vector<string> res;
      7         string crnt;
      8 
      9         if (start == n) return {""};
     10         for (int i = start; i < min(start + 10, n); i++) {
     11             crnt += s[i];
     12             if (!us[i - start].count(crnt)) continue;
     13             for (const auto &s : rec(s, i + 1)) {
     14                 res.push_back(start == 0 ? "" : " ");
     15                 res.back() += crnt + s;
     16             }
     17         }
     18 
     19         return res;
     20     }
     21 
     22   public:
     23     vector<string> wordBreak(const string &s, const vector<string> &wordDict) {
     24         for (const auto &word : wordDict)
     25             us[size(word) - 1].insert(word);
     26         return rec(s);
     27     }
     28 };