Design Search Autocomplete System

Description

null

Solution(javascript)

/* eslint-disable class-methods-use-this */
class TrieNode {
  constructor(val) {
    this.val = val
    this.children = {}
    this.time = 0
    this.end = false
  }
}


class Trie {
  constructor() {
    this.root = new TrieNode('')
  }

  insert(word, time) {
    let parent = this.root
    for (const c of word) {
      if (!parent.children[c]) {
        parent.children[c] = new TrieNode(c)
      }
      parent = parent.children[c]
    }
    parent.end = true
    if (time !== undefined) {
      parent.time += time
    } else {
      parent.time += 1
    }
  }

  searchPrefix(word) {
    let parent = this.root
    for (const c of word) {
      if (!parent.children[c]) {
        return []
      }
      parent = parent.children[c]
    }
    return this.dfs(parent, word)
  }

  dfs(node, prefix) {
    const result = []
    const aux = (node, current = prefix) => {
      if (node.end) {
        result.push([current, node.time])
      }
      Object.values(node.children).forEach((child) => {
        aux(child, current + child.val)
      })
    }
    aux(node)
    return result.sort((a, b) => {
      if (a[1] !== b[1]) {
        return b[1] - a[1]
      }
      return a[0].localeCompare(b[0])
    }).slice(0, 3).map(a => a[0])
  }
}

/**
 * @param {string[]} sentences
 * @param {number[]} times
 */
const AutocompleteSystem = function (sentences, times) {
  this.trie = new Trie()
  sentences.forEach((word, index) => {
    this.trie.insert(word, times[index])
  })
  this.root = this.trie.root
  this.currentNode = this.root
  this.prefix = ''
}

/**
 * @param {character} c
 * @return {string[]}
 */
AutocompleteSystem.prototype.input = function (c) {
  if (c !== '#') {
    this.prefix += c
    if (!this.currentNode || !this.currentNode.children[c]) {
      this.currentNode = null // 注意这里
      return []
    }
    this.currentNode = this.currentNode.children[c]
    return this.trie.dfs(this.currentNode, this.prefix)
  }
  this.trie.insert(this.prefix)
  this.prefix = ''
  this.currentNode = this.root
  return []
}