📑 题目：211. 添加与搜索单词 - 数据结构设计

🚀 本题 LeetCode 传送门

题目大意

设计一个支持以下两种操作的数据结构：void addWord(word)、bool search(word)。search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 “.” 可以表示任何一个字母。

解题思路

  • 设计一个 WordDictionary 的数据结构，要求具有 addWord(word) 和 search(word) 的操作，并且具有模糊查找的功能。
  • 这一题是第 208 题的加强版，在第 208 题经典的 Trie 上加上了模糊查找的功能。其他实现一模一样。

代码

  1. package leetcode
  3. type WordDictionary struct {
  4.  children map[rune]*WordDictionary
  5.  isWord   bool
  6. }
  8. /** Initialize your data structure here. */
  9. func Constructor211() WordDictionary {
  10.  return WordDictionary{children: make(map[rune]*WordDictionary)}
  11. }
  13. /** Adds a word into the data structure. */
  14. func (this *WordDictionary) AddWord(word string) {
  15.  parent := this
  16.  for _, ch := range word {
  17.   if child, ok := parent.children[ch]; ok {
  18.    parent = child
  19.   } else {
  20.    newChild := &WordDictionary{children: make(map[rune]*WordDictionary)}
  21.    parent.children[ch] = newChild
  22.    parent = newChild
  23.   }
  24.  }
  25.  parent.isWord = true
  26. }
  28. /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
  29. func (this *WordDictionary) Search(word string) bool {
  30.  parent := this
  31.  for i, ch := range word {
  32.   if rune(ch) == '.' {
  33.    isMatched := false
  34.    for _, v := range parent.children {
  35.     if v.Search(word[i+1:]) {
  36.      isMatched = true
  37.     }
  38.    }
  39.    return isMatched
  40.   } else if _, ok := parent.children[rune(ch)]; !ok {
  41.    return false
  42.   }
  43.   parent = parent.children[rune(ch)]
  44.  }
  45.  return len(parent.children) == 0 || parent.isWord
  46. }
  48. /**
  49.  * Your WordDictionary object will be instantiated and called as such:
  50.  * obj := Constructor();
  51.  * obj.AddWord(word);
  52.  * param_2 := obj.Search(word);
  53.  */