1. 题目描述

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

• WordDictionary() 初始化词典对象

• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配

• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

示例：

输入：

["WordDictionary","addWord","addWord","addWord","search","search","search","search"]

[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

输出：

[null,null,null,null,false,true,true,true]

解释：

WordDictionary wordDictionary = new WordDictionary();

wordDictionary.addWord("bad");

wordDictionary.addWord("dad");

wordDictionary.addWord("mad");

wordDictionary.search("pad"); // 返回 False

wordDictionary.search("bad"); // 返回 True

wordDictionary.search(".ad"); // 返回 True

wordDictionary.search("b.."); // 返回 True

提示：

• 1 <= word.length <= 25

• addWord 中的 word 由小写英文字母组成

• search 中的 word 由 '.' 或小写英文字母组成

• 最多调用 104 次 addWord 和 search

2. 分析

核心思路：暴力破解！

有时候，抛弃设计，回归问题，也会有不错的收获！O(∩_∩)O哈哈~

提示：本题可以用字典树解决。

3. 代码

// 我就不用字典树，我就是要暴力
type WordDictionary struct {
	// 按长度分组，而后遍历,获取子组可以用map，非.的可以O1查询
	mp map[int][]string
}

func Constructor() WordDictionary {
	return WordDictionary{
		mp: map[int][]string{},
	}
}

func (this *WordDictionary) AddWord(word string) {
	// 去重爷都不做了
	this.mp[len(word)] = append(this.mp[len(word)], word)
}

func (this *WordDictionary) Search(word string) bool {
	return this.match(word)
}

func (this *WordDictionary) match(word string) bool {
	checkWords := this.mp[len(word)]
	for _, checkWord := range checkWords {
		if match(word, checkWord) {
			return true
		}
	}
	return false
}

func match(search, word string) bool {
	for i := range search {
		if search[i] == '.' {
			continue
		}
		if search[i] != word[i] {
			return false
		}
	}
	return true
}