作者：blue

v 信号: Mojitok8275

版权声明：本文为博主原创，转载请注明出处。

211:添加与搜索单词 - 数据结构设计

设计一个支持以下两种操作的数据结构：

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

说明：你可以假设所有单词都是由小写字母 a-z 组成的。

题解同时发表在 leetcode 前缀树 + 队列处理通配符查找

如果不考虑通配符，这道题就是一个典型的前缀树（字典树）问题，我们只需要构造一个前缀树，实现对应的插入和搜索功能即可。

由于题目要求匹配了“.”，因此，在前缀树的搜索时，我们就要对 “.” 进行特殊处理，那我们接下来思考，如何处理通配符？

根据题目要求 . 可以表示任何一个字母，如果一个输入的字符串中包含 . 就意味着，这个查找结果可能会有多个。那么我们来思考带有通配符 . 的字符串的查找结果有几种情况：

• 没有找到对应的单词

  这种情况代表着虽然包含通配符 . 但由于其他位置的字符与字典中的单词字符不能匹配

• 找到一个或多个相应的单词

  这种情况下代表着字典中有一个或多个单词与之相匹配

根据以上两种情况的分析，综合不含通配符单词的查找，我们需要使用集合来保存查找到的 TrieNode 结果。

我们再分析，如果输入的字符串本身不是一个单词，这时我们就要对我们查找到的节点进行过滤，必须存在一个或多个单词字符位数与输入的字符串相匹配，才能视为查找到对应的结果。

实现前缀树

通过上面的分析，我们来构建一个合理的前缀树，这其中的关键就在于设计 Trie 节点结构，所以为了解决我们上述分析的问题，我们需要引入一个布尔变量来表示当前字符串是否是单词，另外为了方便与输入字符串比较长度我们这里通过保存单词字符串的形式处理。

class TrieNode {
    boolean isWord = false;
    String word = "";
    HashMap<Character, TrieNode> children;

TrieNode() {
        children = new HashMap<>();
    }
}

设计好了节点结构以后，我们就来实现前缀树了：

class Trie {
    private TrieNode root;

Trie() {
        root = new TrieNode();
    }

void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode child = cur.children.get(c);
            if (child != null) {
                cur = child;
            } else {
                TrieNode next = new TrieNode();
                cur.children.put(c, next);
                cur = next;
            }
        }
        cur.isWord = true;
        cur.word = word;
    }

boolean search(String word) {
        // ？？
    }

}

通过队列来处理多节点遍历

那么接下来如何对搜索进行实现呢？根据我们开头的分析，由于通配符 . 的存在，在遍历节点时可能需要一次遍历多个节点（例如：一个字符. 匹配出 a b c 三个前缀节点），此时我们自然想到用队列的数据结构比较适合处理这个问题。

boolean search(String word) {
	// 引入队列
	LinkedList<TrieNode> queue = new LinkedList<>();
	queue.add(root);
	// 遍历字符串的索引；
	int index = 0;
	List<TrieNode> res = new ArrayList<>();
	while (!queue.isEmpty() && index < word.length()) {
		int size = queue.size();
		char c = word.charAt(index++);
		for (int j = 0; j < size; j++) {
		TrieNode cur = queue.poll();
			if (c == '.') { // 处理通配符 “.”
				for (Map.Entry<Character, TrieNode> e : cur.children.entrySet()) {
					TrieNode child = e.getValue();
					queue.add(child);
					if(index == word.length()){
						res.add(child);
					}
				}
			} else {
				TrieNode child = cur.children.get(c);
				if (child != null) {
					queue.add(child);
					if(index == word.length()){
						res.add(child);
					}
				} else {
					// nothing to do
					// 如果节点不匹配，则不需要添加到结果集合
				}
			}
		}
	}
	return checkStatus(res, word.length());
}

通过搜索找到临时的结果，此时我们还需要对结果进行筛选处理，保证我们找到的 TrieNode 节点是满足条件的结果。

### 完整代码

public class WordDictionary {
    private Trie mDict;

public WordDictionary() {
        mDict = new Trie();
    }

public void addWord(String word) {
        mDict.insert(word);
    }

public boolean search(String word) {
        return mDict.search(word);
    }

private static class Trie {
        private TrieNode root;

Trie() {
            root = new TrieNode();
        }

void insert(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                TrieNode child = cur.children.get(c);
                if (child != null) {
                    cur = child;
                } else {
                    TrieNode next = new TrieNode();
                    cur.children.put(c, next);
                    cur = next;
                }
            }
            cur.isWord = true;
            cur.word = word;
        }

boolean search(String word) {
            LinkedList<TrieNode> queue = new LinkedList<>();
            queue.add(root);

int index = 0;
            List<TrieNode> res = new ArrayList<>();
            while (!queue.isEmpty() && index < word.length()) {
                int size = queue.size();
                char c = word.charAt(index++);
                for (int j = 0; j < size; j++) {
                    TrieNode cur = queue.poll();
                    if (c == '.') {
                        for (Map.Entry<Character, TrieNode> e : cur.children.entrySet()) {
                            TrieNode child = e.getValue();
                            queue.add(child);
                            if(index == word.length()){
                                res.add(child);
                            }
                        }
                    } else {
                        TrieNode child = cur.children.get(c);
                        if (child != null) {
                            queue.add(child);
                            if(index == word.length()){
                                res.add(child);
                            }
                        } else {
                            // nothing to do
                            // 如果节点不匹配，则不需要添加到结果集合
                        }
                    }
                }
            }
            return checkStatus(res, word.length());
        }

boolean checkStatus(List<TrieNode> res, int len) {
            if(res.isEmpty()) {
                return false;
            }
            int f = 0;
            for (TrieNode n : res) {
                if (n.isWord && n.word.length() == len)
                    f++;
            }
            return f != 0;
        }
    }

private static class TrieNode {
        boolean isWord = false;
        String word = "";
        HashMap<Character, TrieNode> children;

TrieNode() {
            children = new HashMap<>();
        }
    }
}