Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 25

Description

Word Break II

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Constraints:

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.
• Input is generated in a way that the length of the answer doesn't exceed 10⁵.

Solution

struct TrieNode {
  bool end = false;
  TrieNode *child[26] = {};
};
void insert(TrieNode *root, const string &word) {
  TrieNode *cur = root;
  for(auto c : word) {
    if(!cur->child[c - 'a']) cur->child[c - 'a'] = new TrieNode();
    cur = cur->child[c - 'a'];
  }
  cur->end = true;
}
class Solution {
  TrieNode *root;
  int len;
  vector<vector<string>> cache;
  vector<bool> visit;
  void solve(
    const string &s,
    int pos
  ) {
    TrieNode *cur = root;
    if(len == pos) return;
    if(visit[pos]) return;
    int start = pos;
    while(pos < len) {
      if(!cur->child[s[pos] - 'a']) {
        visit[start] = true;
        return;
      }
      cur = cur->child[s[pos] - 'a'];
      pos += 1;
      if(cur->end) {
        solve(s, pos);
        for(const auto &rest : cache[pos]) {
          string result = s.substr(start, pos - start);
          if(rest.size()) {
            result = result + " " + rest;
          }
          cache[start].emplace_back(move(result));
        }
      }
    }
    visit[start] = true;
  }
public:
  vector<string> wordBreak(string s, vector<string>& wordDict) {
    root = new TrieNode();
    len = s.length();
    visit.resize(len + 1);
    cache.resize(len + 1);
    cache[len].push_back("");
    for(const auto &word : wordDict) {
      insert(root, word);
    }
    solve(s, 0);
    return cache[0];
  }
};