LeetCode 211.添加与搜索单词 - 数据结构设计 题解

题目信息

LeetoCode地址: 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目理解

该题是LeetCode 208.实现Trie(前缀树) 题解  的进阶与变体。本质还是通过Trie树插入与查找字符串。

但是该题引入了一个新字符 '.'， 它可以替代任何a到z这个26个小写字母。所在在遍历过程中，不再是一条单一的路径，而是应该沿着树的所有可能分枝进行深入，想起什么了没？没错！就是树的深度遍历。

在进行DFS深度优先遍历时，我们并不需要枚举所有的可能性，毕竟题目仅仅只是需要确定是否存在某字符串，而不是找出所有的匹配的字符串数目。所以当我们遍历到某条路径发现匹配后，即可直接返回。

Trie树 + DFS 写法

在实现时，可以使用Map或者Array存储每个节点链接的下一个节点集合。在效率上区别不大。本文使用Array。在字符串个数m，平均每个字符串字符个数是n的情况下

插入时间复杂度: O(1),因为字符串的长度被限制在了25以内。

最优查询时间复杂度: O(1), 在每个字符都是a到z的情况下，dfs最多调用25次。

最差查询时间复杂度:O(26^25), 在前面24个字符都是'.'的情况下，

额外空间复杂度: O(mn)

public class WordDictionary {
    Trie root;
    public WordDictionary() {
        root = new Trie();
    }

    // 此处和普通的Trie添加字符串的方式是一样的
    public void addWord(String word) {
        Trie current = root;
        for (char c : word.toCharArray()) {
            if (current.nextList[c-'a'] != null) {
                current = current.nextList[c-'a'];
            } else {
                Trie next = new Trie();
                current.nextList[c-'a'] = next;
                current = next;
            }
        }
        current.end = true;
    }

    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    // 此处使用index来表示当前遍历到的字符，比使用word.substring效率要高
    private boolean dfs(Trie root, String word, int index) {
        if (root == null) {
            return false;
        }
        if (index == word.length()) {
            return root.end;
        }
        char c = word.charAt(index);
        // 如果没有遇到. 则按照普通Trie的搜索逻辑
        if (c != '.') {
            return dfs(root.nextList[c - 'a'], word, index+1);
        }
        for (Trie next : root.nextList) {
            // 如果存在匹配成功的情况，就不必继续遍历了，直接返回true
            if (next != null && dfs(next, word, index+1)) {
                return true;
            }
        }
        return false;
    }

    class Trie {
        boolean end;
        Trie[] nextList;
        public Trie() {
            this.end = false;
            this.nextList = new Trie[26];
        }
    }
}