题目：

Implement a trie with insert, search, and startsWith methods.

链接： 

题解：

设计Trie。题目给了很多条件，所以大大简化了我们的思考时间。那么我们就构造一个经典的R-way Trie吧。首先要设计Trie节点，对R-way Trie的话我们使用一个R个元素的数组TrieNode[] next = new TrieNode[R]，本题里R = 26，同时还有一个boolean变量isWord来确定当前节点是否为单词。 然后设计insert，search以及startWith。 具体设计思路完全参考了Sedgewick的课件，非常清楚。二刷要再多多练习计算复杂度以及Tenary-search Trie和Suffix Tree/Suffix Trie的东西，也要看一看Eric Demaine的MIT视频里String那一课。

Time Complexity - O(n)  for each insert，search，startWith，  Space Complexity - O(26ⁿ)， n为word的平均长度。假如m个单词的话 Space Complexity是 - O(m * 26ⁿ)

class TrieNode {    // Initialize your data structure here.    public boolean isWord;    public TrieNode[] next;    private final int R = 26;           // R-way Trie        public TrieNode() {        next = new TrieNode[R];    }}public class Trie {    private TrieNode root;    public Trie() {        root = new TrieNode();    }    // Inserts a word into the trie.    public void insert(String word) {        if(word == null || word.length() == 0)            return;        TrieNode node = root;        int d = 0;                  // depth/distance                while(d < word.length()) {            char c = word.charAt(d);            if(node.next[c - 'a'] == null)                node.next[c - 'a'] = new TrieNode();            node = node.next[c - 'a'];            d++;        }                node.isWord = true;    }    // Returns if the word is in the trie.    public boolean search(String word) {        if(word == null || word.length() == 0)            return false;        TrieNode node = root;        int d = 0;                while(d < word.length()) {            char c = word.charAt(d);            if(node.next[c - 'a'] == null)      // did not find char within word                return false;            node = node.next[c - 'a'];            d++;        }                return node.isWord;    }    // Returns if there is any word in the trie    // that starts with the given prefix.    public boolean startsWith(String prefix) {        if(prefix == null || prefix.length() == 0)            return false;        TrieNode node = root;        int d = 0;                while(d < prefix.length()) {            char c = prefix.charAt(d);            if(node.next[c - 'a'] == null)      // did not find char within prefix                return false;            node = node.next[c - 'a'];            d++;        }                return true;    }}// Your Trie object will be instantiated and called as such:// Trie trie = new Trie();// trie.insert("somestring");// trie.search("key");

 

二刷:

还是写得少，并不熟悉，只有个大概印象，可能要刷三到四遍才会深刻一点。

对于TrieNode的设计:

1. 一般的R-way Trie就是每一个节点TrieNode有R个子节点，我们可以用一个数组来表示子节点。
2. 数组的大小要根据题意来定，比如这道题说明了alphabet = 'a' 到 'z', 那么我们的R就等于26，做一个26-way Trie就可以了。
3. 要有一个boolean变量isWord来表明这个节点是否是单词的结尾。
4. 在Trie里面的首先要初始化一个root节点。  TrieNode root = new TrieNode(); 这个节点我们不保存任何字母。

对于insert

1. 首先处理一下边界条件
2. 设置一个变量d = 0代表深度depth
3. 设置一个TrieNode node = root，这里算是获取一个root的reference
4. 当d < word.length()时，我们根据word.charAt(d) - 'a'来算得 word的第一个字母应该保存的位置index
5. 查看word.next[index]，假如其为空，那么我们要创建一个新的TrieNode。不为空的时候不用管，直接运行6。
6. 更新node = node.next[index]， d++， 继续处理word中的下一个字母
7. 全部遍历完毕以后，设置node.isWord = true，表明root到这个node的路径是一个单词。

对于search和startWith

1. 1 ~ 4步跟insert都一样
2. 查看woird.next[index]，假如其为空直接返回false
3. 更新node = node.next[index], d++，继续查找word中的下一个字母
4. 最后一步，对于Search来说，我们要根据node.isWord来决定是否查找成功。 对于startWith来说我们直接返回true。  

Java:

Time Complexity - O(n)  for each insert，search，startWith，  Space Complexity - O(26ⁿ)， n为word的平均长度。假如m个单词的话， Space Complexity就是是 - O(m * 26ⁿ)

class TrieNode {    // Initialize your data structure here.    TrieNode[] next;    boolean isWord;    int R = 26;   // radix 'a' - 'z'        public TrieNode() {        this.next = new TrieNode[R];    }}public class Trie {    private TrieNode root;    public Trie() {        root = new TrieNode();    }    // Inserts a word into the trie.    public void insert(String word) {        if (word == null || word.length() == 0) return;        TrieNode node = root;        int d = 0;        while (d < word.length()) {            int index = word.charAt(d) - 'a';            if (node.next[index] == null) node.next[index] = new TrieNode();            node = node.next[index];            d++;        }        node.isWord = true;    }    // Returns if the word is in the trie.    public boolean search(String word) {        if (word == null || word.length() == 0) return false;        TrieNode node = root;        int d = 0;        while (d < word.length()) {            int index = word.charAt(d) - 'a';            if (node.next[index] == null) return false;            node = node.next[index];            d++;        }        return node.isWord;    }    // Returns if there is any word in the trie    // that starts with the given prefix.    public boolean startsWith(String prefix) {        if (prefix == null || prefix.length() == 0) return false;        TrieNode node = root;        int d = 0;        while (d < prefix.length()) {            int index = prefix.charAt(d) - 'a';            if (node.next[index] == null) return false;            node = node.next[index];            d++;        }        return true;    }}// Your Trie object will be instantiated and called as such:// Trie trie = new Trie();// trie.insert("somestring");// trie.search("key");

 

 

 

 

Reference:

http://algs4.cs.princeton.edu/52trie/

https://en.wikipedia.org/wiki/Trie

https://en.wikipedia.org/wiki/Suffix_tree