Replace Words

Description

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 successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor 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"

Example 3:

Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"

Example 4:

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

Example 5:

Input: dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
Output: "it is ab that this solution is ac"

 

Constraints:

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case letters.
• 1 <= sentence.length <= 10^6
• 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]
• Each two consecutive words in sentence will be separated by exactly one space.
• sentence does not have leading or trailing spaces.

Solution(javascript)

class TrieNode {
  constructor(val) {
    this.val = val
    this.children = {}
    this.word = false
  }
}
/**
 * Initialize your data structure here.
 */
const Trie = function () {
  this.root = new TrieNode('')
}

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
  let node = this.root
  for (const c of word) {
    if (!node.children[c]) {
      node.children[c] = new TrieNode(c)
      node = node.children[c]
    } else {
      node = node.children[c]
    }
  }
  node.word = true
}

/**
 * Returns if the word is in the trie.
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function (word) {
  let node = this.root
  for (const c of word) {
    if (!node.children[c]) {
      return false
    }
    node = node.children[c]
  }
  return node.word
}

/**
 * Returns if there is any word in the trie that starts with the given prefix.
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function (prefix) {
  let node = this.root
  for (const c of prefix) {
    if (!node.children[c]) {
      return false
    }
    node = node.children[c]
  }
  return true
}

Trie.prototype.successor = function (str) {
  let node = this.root
  let index = 0
  for (const c of str) {
    if (!node.children[c]) {
      return -1
    }
    node = node.children[c]
    if (node.word) {
      return index
    }
    index += 1
  }
  return -1
}


// @lc code=start

/**
 * @param {string[]} dict
 * @param {string} sentence
 * @return {string}
 */
const replaceWords = function (dict, sentence) {
  const trieTree = new Trie()
  dict.forEach((d) => {
    trieTree.insert(d)
  })
  return sentence.split(' ').map((word) => {
    const index = trieTree.successor(word)
    if (index === -1) {
      return word
    }
    return word.slice(0, index + 1)
  }).join(' ')
}
// @lc code=end