问题

求出给定字符串数组的最大公共前缀["hello","helloworld","help"]

用途

自动完成

拼写检查

ip路由

T9文本预测

猜字游戏

还有其他几种数据结构，例如平衡树和哈希表，它们使我们可以在字符串数据集中搜索单词。那为什么我们需要 trie 呢？

尽管哈希表在查找key时具有 O(1) 时间复杂度，但在以下操作中效率不高：

• 查找具有公共前缀的所有键。
• 按字典顺序枚举字符串数据集。

Trie 优于哈希表的另一个原因是，随着哈希表大小的增加，会出现大量哈希冲突，并且搜索时间复杂度可能会恶化到 O(n)，其中 n 是插入的键数。在存储许多具有相同前缀的键时，与 Hash Table 相比，Trie 可以使用更少的空间。在这种情况下，使用 trie 的时间复杂度仅为 O(m)，其中 m 是key长度。

在平衡树中搜索一个键需要 O(m log n)时间复杂度。

Trie节点结构

Trie是一棵有根的树。其节点具有以下字段：

• 与其子级的最大 R 链接，其中每个链接对应于数据集字母表中的一个 R 字符值。
• 在本文中，我们假设 R 为 26，即小写拉丁字母的数量。
• 布尔字段，它指定节点是否对应于键的末尾，或者只是一个键前缀。
• 当前节点下级节点个数（非必须，我们为了解决最长公共串才加上）

public class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    int size = 0;

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

    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;
        size++;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }

    public int getLinks() {
        return size;
    }
}

插入查询类

public 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 currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        //注意这里，设置end的节点是不包含最后一个字符的
        node.setEnd();
    }
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }
        return node;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }

    public String searchLongestPrefix(String s){
        TrieNode node = root;
        StringBuilder sb = new StringBuilder();
        for(char c : s.toCharArray()){
            if(node.containsKey(c) && node.getLinks() == 1 && !node.isEnd()){
                sb.append(c);
                node = node.get(c);
            }else{
                return sb.toString();
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String[] link = new String[]{"hello","helloworld","help"};
        Trie trie = new Trie();
        for (String s : link) {
            trie.insert(s);
        }
        System.out.println(trie.searchLongestPrefix(link[link.length-1]));

    }
}