leetcode 676. Implement Magic Dictionary | 676. 实现一个魔法字典（DFS+Trie 前缀树）

admin管理员组

文章数量:1636948

题目

https://leetcode/problems/implement-magic-dictionary/description/

题解

题意理解

前缀树问题，大意是是让你在字典中找到是否存在与当前字符串有 1 个字符的 diff 的匹配。参考了：leetcode 208. Implement Trie (Prefix Tree) | 208. 实现 Trie 前缀树（Java） 的代码，并做了一些修改。

修改的时候，需要注意的细节比较多。比如从 [“hello”,“hallo”] 中查找 “hello” 时，应该返回 true，而从 [“hello”] 中查找 “hello” 时，应该返回 false。这就要求我们不能直接去匹配，而是需要故意去尝试走不匹配的路径。

整体思路

我们规定一种 tolerance 机制：将有一个字符匹配失败的情况作为 fault，而这种 fault 是可以被容忍、且必须存在的，只有在遇到了 fault 之后，剩下的字符串才可以安心地进行 one-way 匹配。

遇到 fault 之后，我们将剩下的字符串进行经典的 Trie search, 将查找的结果称为 failover（形不形象？）。注：在代码中，!tolerance 就是遇到过 fault 的意思。

正确性证明：在 searchPrefix 函数中，只有在 !tolerance，且成功匹配剩余所有字符的情况下，才会返回 failover 节点。所以最后只需要对 failover 进行判断，如果 failover 非空并且 failover.isEnd 的话，说明成功的找到了一个包含 1 个 diff 字符的匹配。

代码

时间复杂度比较难以计算，运行效率还不错。

class Node {
    Node[] map;
    boolean isEnd;

    public Node() {
        this.map = new Node['z' - 'a' + 1];
    }

    public Node get(char c) {
        return map[c - 'a'];
    }

    public Node put(char c) {
        Node node = new Node();
        map[c - 'a'] = node;
        return node;
    }
}

class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        char[] chars = word.toCharArray();
        Node cur = root;
        for (int i = 0; i < chars.length; i++) {
            if (cur.get(chars[i]) != null) {
                cur = cur.get(chars[i]);
            } else {
                cur = cur.put(chars[i]);
            }
            if (i == chars.length - 1) {
                cur.isEnd = true;
            }
        }
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        Node node = searchPrefix(root, word, 0, true);
        return node != null && node.isEnd;
    }

    // 从node开始，在是否剩余tolerance的情况下，是否能匹配从i开始的后续字符串
    public Node searchPrefix(Node node, String str, int i, boolean tolerance) {
        if (node == null) return null;
        if (i == str.length()) return tolerance ? null : node;

        Node cur = node;
        if (!tolerance) { // 已无tolerance，直接匹配
            for (int j = i; j < str.length(); j++) {
                char c = str.charAt(j);
                if (cur.get(c) == null) return null;
                else cur = cur.get(c);
            }
            return cur;
        } else {  // 有tolerance，先DFS消耗tolerance, 再递归匹配
            for (int j = 0; j < cur.map.length; j++) {
                // 当 j==str.charAt(i)-'a' 时，此次不消耗tolerance
                // 当 j!=str.charAt(i)-'a' 时，此次消耗tolerance
                Node failover = searchPrefix(cur.map[j], str, i + 1, j == str.charAt(i) - 'a');
                if (failover != null && failover.isEnd) return failover;
            }
        }
        return null;
    }
}

class MagicDictionary {
    Trie trie;

    public MagicDictionary() {
        trie = new Trie();
    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            trie.insert(s);
        }
    }

    public boolean search(String searchWord) {
        return trie.search(searchWord);
    }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */

本文标签： 前缀字典魔法implementLeetCode