题目描述（中等难度）

设计一个数据结构，实现 add 方法添加字符串，search 查找字符串，所查找的字符串可能含有 . ，代表任意的字符。

解法一 暴力

来个暴力的方法，用 HashSet 存入所有的字符串。当查找字符串的时候，我们首先判断 set 中是否存在，如果存在的话直接返回 true 。不存在的话，因为要查找的字符串中可能含有 . ，接下来我们需要遍历 set ，一个一个的进行匹配。

class WordDictionary { HashSet<String> set; /** Initialize your data structure here. */ public WordDictionary() { set = new HashSet<>(); } /** Adds a word into the data structure. */ public void addWord(String word) { set.add(word); } /** * Returns if the word is in the data structure. A word could contain the * dot character '.' to represent any one letter. */ public boolean search(String word) { if (set.contains(word)) { return true; } for (String s : set) { if (equal(s, word)) { return true; } } return false; } private boolean equal(String s, String word) { char[] c1 = s.toCharArray(); char[] c2 = word.toCharArray(); int n1 = s.length(); int n2 = word.length(); if (n1 != n2) { return false; } for (int i = 0; i < n1; i++) { //. 代表任意字符，跳过 if (c1[i] != c2[i] && c2[i] != '.') { return false; } } return true; } } 

当然，由于有些暴力，出现了超时。

至于优化的话，我们不要将加入的字符串一股脑的放入一个 set 中，可以通过长度进行分类，将长度相同的放到一个 set 中。这样一个一个匹配的时候，规模会减小一些。

class WordDictionary { HashMap<Integer,HashSet<String>> map; /** Initialize your data structure here. */ public WordDictionary() { map = new HashMap<>(); } /** Adds a word into the data structure. */ public void addWord(String word) { int n = word.length(); //将字符串加入对应长度的 set 中 if (map.containsKey(n)) { HashSet<String> set = map.get(n); set.add(word); } else { HashSet<String> set = new HashSet<String>(); set.add(word); map.put(n, set); } } /** * Returns if the word is in the data structure. A word could contain the * dot character '.' to represent any one letter. */ public boolean search(String word) { HashSet<String> set = map.getOrDefault(word.length(), new HashSet<String>()); if (set.contains(word)) { return true; } for (String s : set) { if (equal(s, word)) { return true; } } return false; } private boolean equal(String s, String word) { char[] c1 = s.toCharArray(); char[] c2 = word.toCharArray(); int n1 = s.length(); int n2 = word.length(); if (n1 != n2) { return false; } for (int i = 0; i < n1; i++) { if (c1[i] != c2[i] && c2[i] != '.') { return false; } } return true; } } 

虽然上边的解法在 leetcode 中 AC 了，但其实很大程度上取决于 test cases 中所有字符串长度的分布，如果字符串长度全部集中于某个值，上边的解法的优化其实是无能为力的。

上边是按长度分类进行添加的，同样的我们还可以按照字符串的开头字母进行分类。当然，算法的速度同样也依赖于数据的分布，适用于数据分布均匀的情况。

解法二 前缀树

前几天在 208 题 刚做了前缀树，这里的话我们也可以通过前缀树进行存储，这样查找字符串就不用依赖于字符串的数量了。

代码的话在前缀树的基础上改一下就可以，大家可以先看一下 208 题。对于字符串中的 . ，我们通过递归去查找。

class WordDictionary { class TrieNode { TrieNode[] children; boolean flag; public TrieNode() { children = new TrieNode[26]; flag = false; for (int i = 0; i < 26; i++) { children[i] = null; } } } TrieNode root; /** Initialize your data structure here. */ public WordDictionary() { root = new TrieNode(); } /** Adds a word into the data structure. */ public void addWord(String word) { char[] array = word.toCharArray(); TrieNode cur = root; for (int i = 0; i < array.length; i++) { // 当前孩子是否存在 if (cur.children[array[i] - 'a'] == null) { cur.children[array[i] - 'a'] = new TrieNode(); } cur = cur.children[array[i] - 'a']; } // 当前节点代表结束 cur.flag = true; } /** * Returns if the word is in the data structure. A word could contain the * dot character '.' to represent any one letter. */ public boolean search(String word) { return searchHelp(word, root); } private boolean searchHelp(String word, TrieNode root) { char[] array = word.toCharArray(); TrieNode cur = root; for (int i = 0; i < array.length; i++) { // 对于 . , 递归的判断所有不为空的孩子 if(array[i] == '.'){ for(int j = 0;j < 26; j++){ if(cur.children[j] != null){ if(searchHelp(word.substring(i + 1),cur.children[j])){ return true; } } } return false; } // 不含有当前节点 if (cur.children[array[i] - 'a'] == null) { return false; } cur = cur.children[array[i] - 'a']; } // 当前节点是否为是某个单词的结束 return cur.flag; } } 

解法三

再分享一个 leetcode 上边的大神 @StefanPochmann 的一个想法，直接利用正则表达式。

我就不细讲了，直接看代码吧，很简洁。

import re class WordDictionary: def __init__(self): self.words = '#' def addWord(self, word): self.words += word + '#' def search(self, word): return bool(re.search('#' + word + '#', self.words)) 

我用 java 改写了一下。

import java.util.regex.*; class WordDictionary { StringBuilder sb; public WordDictionary() { sb = new StringBuilder(); sb.append('#'); } public void addWord(String word) { sb.append(word); sb.append('#'); } public boolean search(String word) { Pattern p = Pattern.compile('#' + word + '#'); Matcher m = p.matcher(sb.toString()); return m.find(); } } 

不过遗憾的是，java 在 leetcode 上这个解法会超时，python 没什么问题。当然优化的话，我们可以再像解法一那样对字符串进行分类，这里就不再写了。

上边的解法的关键就是，用 # 分割不同单词，以及查找的时候查找 # + word + # ，很妙。

总

解法一是直觉上的解法，分类的思想也经常用到。解法二的话，需要数据结构的积累，刚好前几题实现了前缀树，空间换时间，这里也就直接想到了。解法三的话，大概只有大神能想到了，一种完全不同的视角，很棒。