image.png

题解

这道题的目的是实现一个 Trie 数据结构，Trie 实现相对简单：

  1. class TrieNode {
  2.   isWord: boolean;
  3.   next: Map<string, TrieNode> = new Map()
  5.   constructor(isWord = false) {
  6.     this.isWord = isWord
  7.   }
  8. }
  9. class Trie {
  10.   root: TrieNode
  12.     constructor() {
  13.       this.root = new TrieNode()
  14.     }
  16.     insert(word: string): void {
  17.       // 1. 遍历 word 中的每一个字符
  18.       // 2. 查看字符是否已经存在于 TrieNode 中，如果不存在，则将该字符存到 Trie 中
  19.       // 3. 最后一个字符标记为单词的结尾
  20.       let current = this.root
  21.       for(const c of word) {
  22.         if (!current.next.get(c)) {
  23.           current.next.set(c, new TrieNode()) 
  24.         }
  25.         current = current.next.get(c) as TrieNode
  26.       }
  27.       current.isWord = true
  28.     }
  30.     search(word: string): boolean {
  31.       // 1. 遍历 word 中的每一个字符
  32.       // 2. 如果某个字符不存在，则返回 false
  33.       // 3. 如果已经遍历到最后一个字符，并且都存在 Trie 中，那么则判断最后一个字符是否有 isWord 的标识
  34.       let current = this.root
  35.       for(const c of word) {
  36.         if (current.next === null) {
  37.           return false
  38.         }
  39.         const nextTrieNode = current.next.get(c)
  40.         if (!nextTrieNode) {
  41.           return false
  42.         }
  44.         current = nextTrieNode
  45.       }
  46.       return current.isWord
  47.     }
  49.     startsWith(prefix: string): boolean {
  50.       // 1. 遍历 prefix 中的每一个字符
  51.       // 2. 如果某个字符不存在，直接返回 false，否则返回 true
  53.       let current = this.root
  54.       for(const c of prefix) {
  55.         if (current.next === null) {
  56.           return false
  57.         }
  58.         const nextTrieNode = current.next.get(c)
  59.         if (!nextTrieNode) {
  60.           return false
  61.         }
  62.         current = nextTrieNode
  63.       }
  65.       return true
  66.     }
  67. }
  69. /**
  70.  * Your Trie object will be instantiated and called as such:
  71.  * var obj = new Trie()
  72.  * obj.insert(word)
  73.  * var param_2 = obj.search(word)
  74.  * var param_3 = obj.startsWith(prefix)
  75.  */