单词替换

题目

在英语中, 我们有一个叫做 词根(root) 的概念, 可以词根后面添加其他一些词组成另一个较长的单词, 我们称这个词为 继承词(successor). 例如, 词根 an, 跟随着单词 other(其他), 可以形成新的单词 another(另一个).

现在, 给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence. 你需要将句子中的所有继承词用词根替换掉. 如果继承词有许多可以形成它的词根, 则用最短的词根替换它.

你需要输出替换之后的句子.

提示:

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] 仅由小写字母组成.
• 1 <= sentence.length <= 10⁶
• sentence 仅由小写字母和空格组成.
• sentence 中单词的总量在范围 [1, 1000] 内.
• sentence 中每个单词的长度在范围 [1, 1000] 内.
• sentence 中单词之间由一个空格隔开.
• sentence 没有前导或尾随空格.

示例

输入: (dictionary = ['cat', 'bat', 'rat']),
  (sentence = 'the cattle was rattled by the battery')
输出: 'the cat was rat by the bat'

输入: (dictionary = ['a', 'b', 'c']),
  (sentence = 'aadsfasf absbs bbab cadsfafs')
输出: 'a a b c'

题解

JavaScript - 朴素解法

朴素解法都能想到, 先把 dictionary 按 root 长度排序, 这样的目的是给单词先匹配最短前缀.

然后遍历 sentence 中的每个单词, 并为每个单词匹配前缀, 如果匹配上就替换成前缀, 否则还是原单词.

/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
var replaceWords = function (dictionary, sentence) {
  dictionary.sort((a, b) => a.length - b.length)
  const words = sentence.split(' ')
  const res = []

  for (const word of words) {
    let curr = word
    for (const root of dictionary) {
      if (curr.startsWith(root)) {
        curr = root
        break
      }
    }
    res.push(curr)
  }

  return res.join(' ')
}

JavaScript - 前缀树

第二种方式是前缀树, 把词根放到前缀树中, 然后对每个单词匹配前缀即可.

/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
var replaceWords = function (dictionary, sentence) {
  const trie = new Trie()
  const words = sentence.split(' ')
  for (const root of dictionary) {
    trie.insert(root)
  }

  for (let i = 0; i < words.length; i++) {
    words[i] = trie.getPrefix(words[i])
  }

  return words.join(' ')
}

class Trie {
  constructor() {
    this.children = {}
  }

  insert(word) {
    let node = this.children

    for (const ch of word) {
      if (!node[ch]) {
        node[ch] = {}
      }
      node = node[ch]
    }
    node.isEnd = true
  }

  search(word) {
    let node = this.searchPrefix(word)
    return !!node && node.isEnd
  }

  searchPrefix = function (prefix) {
    let node = this.children
    for (const ch of prefix) {
      if (!node[ch]) {
        return null
      }
      node = node[ch]
    }
    return node
  }

  getPrefix(word) {
    let str = ''
    for (let i = 0; i < word.length; i++) {
      str += word[i]
      if (this.search(str)) return str
    }
    return word
  }
}