208.实现-trie-前缀树.md

208.实现-trie-前缀树

/*
 * @lc app=leetcode.cn id=208 lang=typescript
 *
 * [208] 实现 Trie (前缀树)
 */

// @lc code=start

class Trie {
  constructor() {}

  insert(word: string): void {}

  search(word: string): boolean {}

  startsWith(prefix: string): boolean {}
}

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */
// @lc code=end

解法 1: 使用哈希表

type TrieNode = { [key: string]: TrieNode } & { isEnd?: boolean }
class Trie {
  _root: TrieNode = {}
  constructor() {}

  insert(word: string): void {
    let node = this._root
    for (const c of word) {
      node = node[c] || (node[c] = {})
    }
    node.isEnd = true
  }

  searchPrefix(word: string): TrieNode | null {
    let node = this._root
    for (const c of word) {
      if (!node[c]) return null
      node = node[c]
    }
    return node
  }

  search(word: string): boolean {
    return !!this.searchPrefix(word)?.isEnd
  }

  startsWith(prefix: string): boolean {
    return !!this.searchPrefix(prefix)
  }
}

Case

test.each([
  {
    input: {
      operations: ['Trie', 'insert', 'search', 'search', 'startsWith', 'insert', 'search'],
      params: [[], ['apple'], ['apple'], ['app'], ['app'], ['app'], ['app']],
    },
    output: [null, null, true, false, true, null, true],
  },
])(`input: n = $input.n`, ({ input: { operations, params }, output }) => {
  let trie: Trie = new Trie()
  const res: any[] = [null]
  for (let i = 1; i < operations.length; i++) {
    const operation: 'insert' | 'search' | 'startsWith' = operations[i] as any
    res.push(trie[operation](params[i][0]) ?? null)
  }

  expect(res).toEqual(output)
})