LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 先通过 #139 的解法判断能否拆分，如果可以拆分则用回溯法拼接结果

class Solution {
 public:
  vector<string> wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> wordSet{begin(wordDict), end(wordDict)};
    vector<bool> dp(size(s) + 1);
    dp[0] = true;
    for (int i = 1; i < size(dp); ++i) {
      for (int j = 0; j < i; ++j) {
        if (dp[j] && wordSet.count(s.substr(j, i - j))) {
          dp[i] = true;
          break;
        }
      }
    }
    vector<string> res;
    if (!dp.back()) {
      return res;
    }
    vector<string> path;
    dfs(wordSet, dp, res, path, s, 0);
    return res;
  }

  void dfs(unordered_set<string>& wordSet, vector<bool>& dp,
           vector<string>& res, vector<string>& path, string_view s, int n) {
    if (!dp[n]) {
      return;
    }
    if (n == size(s)) {
      string t;
      for (int i = 0; i < size(path) - 1; ++i) {
        t += (path[i] + " ");
      }
      t += path.back();
      res.emplace_back(t);
    }
    for (int i = n; i < size(s); ++i) {
      string t{s.substr(n, i - n + 1)};
      if (wordSet.count(t)) {
        path.emplace_back(t);
        dfs(wordSet, dp, res, path, s, i + 1);
        path.pop_back();
      }
    }
  }
};