leetcode——实现Trie(前缀树)

题目

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例

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

看到这个题一点思路都没有，前缀树是什么。就去查了一下概念什么是前缀树。发现前缀树通常被用来查找字符串的公共前缀，是通过空间换取时间的一种方法。一般创建前缀树结点的时候里面都有两个变量，一个布尔变量isTrie和一个结点数据，长度为26，他们的下标代表当前字符串中的字符存在。

给出一组单词，inn,int,at,age,adv,ant,可以得到下面的Trie:

每条边上的字母代表上一个结点中的children数组中对应的位置new出的新的结点。每个结点对应一项前缀。叶结点对应最长前缀，即单词本身。可以通过这种方式判断公共前缀。

下面来看这道题怎么写：

class Trie{
    public TrieNode root;
    public Trie(){
        root = new TrieNode();
    }
    
    //创建字典树
    public void insert(String s){
        TrieNode node = this.root;
        for(char ch : s.toCharArray()){
            if(node.children[ch - 'a'] == null){
                node.children[ch-'a'] = new TrieNode();
            }
            node = node.children[ch-'a'];
        }
        node.val = s;
    }
    //在字典树中查找是否包含当前单词
    public boolean search(String s){
        TrieNode node = this.root;
        for(char ch : s.toCharArray()){
            if(node.children[ch-'a'] != null) {
                return false;
            }
            node = node.children[ch-'a'];
        }
        return node.val.equals(s);
    }
    //查找是否包含前缀
    public boolean startWith(String s){
        TrieNode node = this.root;
        for(char ch : s.toCharArray()){
            if(node.children[ch-'a'] == null){
                return false;
            }
            node = node.children[ch-'a'];
        }
        return true;
    }
    
    //创建字典树结点结构 26代表26个字母，根据不同的字母创建结点
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        String val;
    }
}

还是要多刷算法，加油！！！