问题

求出给定字符串数组的最大公共前缀["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]));    }}