Word Break II

Question

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

Example

Gieve s = lintcode,
dict = ["de", "ding", "co", "code", "lint"].
A solution is ["lint code", "lint co de"].

Answer

RunTime : 902ms

class Solution {
public:
 /*
 * @param s: A string
 * @param dict: A dictionary of words dict
 * @return: A boolean
 */
 vector<string> wordBreak(string &s, unordered_set<string> &dict) {
  // write your code here
  result.clear();
  if (s.length() <= 0)
   return result;
  bool found = true;
  for (auto c : s) {
   bool in = false;
   for (auto d : dict) {
    if (in)
     break;
    for (auto e : d) {
     if (e == c) {
      in = true;
      break;
     }
    }
   }
   if (!in) {
    found = false;
    break;
   }
  }
  if (!found)
   return result;
  Trie trie;
  for (auto d : dict)
   trie.insert(d);
  string bw;
  wordBreakHelp(s, trie, 0, bw);
  return result;
 }
private:
 vector<string> result;
 struct TrieNode {
  TrieNode() {
   for (int i = 0; i < 26; i++) {
    next[i] = 0;
   }
   s = 0;
  }
  int s;
  TrieNode* next[26];
 };
 class Trie {
 public:
  Trie() {
   root = new TrieNode();
  }
  inline void deleteHelper(TrieNode* root) {
   if (root) {
    for (int i = 0; i < 26; i++) {
     deleteHelper(root->next[i]);
    }
    delete root;
   }
  }
  ~Trie() {
   deleteHelper(root);
   root = 0;
  }
  void insert(string& s) {
   TrieNode* iter = root;
   for (auto c : s) {
    if (iter->next[c - 'a'] == 0)
     iter->next[c - 'a'] = new TrieNode();
    iter = iter->next[c - 'a'];
   }
   iter->s = s.length();
  }
  unordered_set<int> search(string& s, int pos) {
   TrieNode* iter = root;
   unordered_set<int> words;
   for (size_t i = pos; i < s.length(); i++) {
    char c = s[i];
    if (iter->next[c - 'a'] == 0)
     break;
    if (iter->s > 0) {
     words.insert(iter->s);
    }
    iter = iter->next[c - 'a'];
   }
   if (iter->s > 0) {
    words.insert(iter->s);
   }
   return words;
  }
 private:
  TrieNode* root;
 };
 inline void wordBreakHelp(string& s, Trie& trie, int pos, string& bw) {
  unordered_set<int> words = trie.search(s, pos);
  if (words.size() > 0) {
   for (auto word : words) {
    string bwd = bw;
    if (bwd.empty())
     bwd = s.substr(pos, word);
    else {
     bwd.append(" ");
     bwd.append(s.substr(pos, word));
    }
    if ((pos + word) == s.length()) {
     result.push_back(bwd);
    }
    else {
     wordBreakHelp(s, trie, pos + word, bwd);
    }
   }
  }
 }
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️