648.单词替换.md

648.单词替换

/*
 * @lc app=leetcode.cn id=648 lang=typescript
 *
 * [648] 单词替换
 */

// @lc code=start
// type TrieNode = Partial<Record<'a' | 'b' | 'c', Trie | undefined>>
// type Temp={...TrieNode}
function replaceWords(dictionary: string[], sentence: string): string {}
// @lc code=end

解法 1: 字典树

type Node = {
  done?: boolean
  word?: string
  children: {
    [key: string]: Node
  }
}
function replaceWords(dictionary: string[], sentence: string): string {
  const root: Node = { children: {} }
  for (let s of dictionary) {
    let node = root
    for (let ch of s) {
      if (node.children[ch] === undefined) node.children[ch] = { children: {} }
      node = node.children[ch]
    }
    node.done = true
    node.word = s
  }

  const res = sentence.split(' ')
  for (let [i, word] of res.entries()) {
    let node = root
    for (let ch of word) {
      node = node.children[ch]
      if (!node) break
      if (node.done) {
        res[i] = node.word
        break
      }
    }
  }
  return res.join(' ')
}

Case

test.each([
  {
    input: { dictionary: ['cat', 'bat', 'rat'], sentence: 'the cattle was rattled by the battery' },
    output: 'the cat was rat by the bat',
  },
  { input: { dictionary: ['a', 'b', 'c'], sentence: 'aadsfasf absbs bbab cadsfafs' }, output: 'a a b c' },
])(
  'input: dictionary = $input.dictionary, sentence = $input.sentence',
  ({ input: { dictionary, sentence }, output }) => {
    expect(replaceWords(dictionary, sentence)).toEqual(output)
  },
)