【每日算法Day 52】前缀树

Trie 树又称“前缀树”，它的典型应用对象是字符串，可以用于保存、统计。其特点是：用边表示字符，当走到叶子结点的时候，沿途所经过的边组成了一个字符串。其优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

前缀树的用途很多，例如搜索引擎自动补全，IP路由最长前缀匹配。哈希表可以在O(1)的时间内寻找键值但是却不能高效地找到具有同一前缀的全部键值、也不能按照字典序枚举字符串数据集。另外在存储有较多相同前缀的键时更节省空间。

LeetCode 208. 实现 Trie (前缀树) (opens new window)

题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。

示例

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

解题思路

在前缀树中，每个字符是存在于路径之中的（而不是节点），所以构造节点时总是创建一个空的“路径选择列表”（也就是节点的引用数组），然后在插入表达某个字符的路径时才为对应数组中的引用赋值。同时，使用isEnd来标记当前节点是否是某一选择结束后的节点。这就说明，前缀树的叶子节点中的引用数组中的引用总是全为空的。

class Trie {
    //只保存根节点
    private TrieNode root;

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

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curr = word.charAt(i);
            if (!node.containsKey(curr)) {
                node.put(curr, new TrieNode());
            }
            node = node.get(curr);
        }
        node.setEnd();
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curr = word.charAt(i);
            if (node.containsKey(curr)) {
                node = node.get(curr);
            } else {
                return false;
            }
        }
        //如果不是end说明word是存入前缀树的另一个词的前缀
        return node.isEnd();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char curr = prefix.charAt(i);
            if (node.containsKey(curr)) {
                node = node.get(curr);
            } else {
                return false;
            }
        }
        //只要没返回false则说明前缀都匹配了
        return true;
    }
}

//节点
class TrieNode{
    private TrieNode[] links;
    private boolean isEnd;

    public TrieNode() {
        links = new TrieNode[26];
    }

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch-'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }
}

LeetCode 211. 添加与搜索单词 - 数据结构设计 (opens new window)

题目描述

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

void addWord(word)
boolean search(word)

search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。你可以假设所有单词都是由小写字母 a-z 组成的。

示例

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

解题思路

添加单词依然和上一题一样直接使用前缀树，搜索完成的条件是按字符串走完全部的路径并且最后到达的节点被标记为end。唯一的不同是通配符.的处理。在遇到点号时，要对所有不为空的叶子节点继续进行递归搜索（跳过一个字符的位置），如果都没有匹配的则返回false。

public class No211_AddAndSearchWord {
    private TrieNode root;

    public No211_AddAndSearchWord() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curr = word.charAt(i);
            if (!node.containsKey(curr)) {
                node.put(curr, new TrieNode());
            }
            node = node.get(curr);
        }
        node.setEnd();
    }

    public boolean search(String word) {
        TrieNode node = root;
        return search(word, 0, node);
    }

    private boolean search(String word, int index,TrieNode node) {
        //如果目标字符串已经全部匹配且没有返回false，这时根据该节点有没有isEnd标记来确定搜索结果
        if (index == word.length()) {
            return node.isEnd();
        }
        char ch = word.charAt(index);
        if (ch == '.') {
            //这里需要把TrieNode中引用数组的private修饰符去掉或者直接用作内部类
            for (TrieNode next : node.links) {
                if (next != null && search(word, index + 1, next))
                    return true;
            }
            return false;
        } else {
            return node.containsKey(ch) && search(word, index + 1, node.get(ch));
        }
    }
}