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

June LeetCoding Challenge 7

Description

Replace Words

In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Constraints:

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case letters.
• 1 <= sentence.length <= 106
• sentence consists of only lower-case letters and spaces.
• The number of words in sentence is in the range [1, 1000]
• The length of each word in sentence is in the range [1, 1000]
• Every two consecutive words in sentence will be separated by exactly one space.
• sentence does not have leading or trailing spaces.

Solution

struct TrieNode {
  bool isEnd;
  TrieNode *next[26];
  TrieNode() : isEnd(false) {
    for(int i = 0; i < 26; ++i) next[i] = nullptr;
  }
};

void insertTrie(string &s, TrieNode *root) {
  TrieNode *cur = root;
  for(auto c : s) {
    if(!cur->next[c - 'a']) {
      cur->next[c - 'a'] = new TrieNode();
    }
    cur = cur->next[c - 'a'];
  }
  cur->isEnd = true;
}

class Solution {
public:
  string replaceWords(vector<string>& dictionary, string sentence) {
    TrieNode *root = new TrieNode();
    for(auto &word : dictionary) {
      insertTrie(word, root);
    }
    string answer;
    bool ok = true;
    bool found = false;
    TrieNode *current = root;
    for(int i = 0; i < sentence.length(); ++i) {
      if(!ok && sentence[i] != ' '){
        answer.push_back(sentence[i]);
      } else if(sentence[i] != ' ' && !found) {
        current = current->next[sentence[i] - 'a'];
        answer.push_back(sentence[i]);
        if(current == nullptr) ok = false;
        else if(current->isEnd) found = true;
      }
      if(sentence[i] == ' ') {
        answer.push_back(' ');
        ok = true;
        found = false;
        current = root;
      }
    }
    return answer;
  }
};