本文共 1850 字，大约阅读时间需要 6 分钟。

链接：

大意：

要求实现添加单词以及查找单词的数据结构及操作。其中，带查找的单词所含字符为'a'-'z'或者'.'。其中'.'可以代表任意一个小写字母。例子：

思路：

使用前缀树的数据结构：，只不过是需要多处理一种'.'的情况。当遇到'.'的时候，可以使用dfs依次遍历该node的所有children（最多26个children）。

若该node的所有children都无法使得其成为已添加的单词，则返回false。

若该node中的某一个child可以使其成为已添加的单词，则返回true。

代码：

class WordDictionary {    static class Node {        Node[] children = null;        boolean isWord;        public Node() {            children = new Node[26];        }    }    Node root = null;    /** Initialize your data structure here. */    public WordDictionary() {        root = new Node();    }        /** Adds a word into the data structure. */    public void addWord(String word) {        Node r = root;        for (char c : word.toCharArray()) {            if (r.children[c - 'a'] == null)                r.children[c - 'a'] = new Node();            r = r.children[c - 'a'];        }        r.isWord = 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 search(word, 0, root);    }    // 基于dfs start为当前字符串的起始位置（使用start而不是用substring，更能提升效率）    public boolean search(String word, int start, Node r) {        while (start < word.length()) {            char c = word.charAt(start);            if (c != '.') {                if (r.children[c - 'a'] == null)                    return false;                r = r.children[c - 'a'];            } else {                for (Node node : r.children) {                    if (node != null) {                        if (search(word, start + 1, node))                            return true;                    }                }                // 这个'.'为任意字符都无法使得该字符串为已添加的字符串                return false;            }            start++;        }        return r.isWord;    }}

结果：

结论：

算是一个数据结构和算法结合的小demo了。。

转载地址：http://jaesi.baihongyu.com/