算法-数据结构-实现 Trie (前缀树)

小咪咪 2023-02-13 14:37 60阅读 0赞

# 算法-数据结构-实现 Trie (前缀树) #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/implement-trie-prefix-tree/

## 1.2 题目描述 ##

实现一个 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  
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。  
保证所有输入均为非空字符串。

# 2 递归版 #

## 2.1 思路 ##

## 2.2 代码 ##

class Trie { 
        private Trie[] children;
        private boolean is_end;
        /** Initialize your data structure here. */
        public Trie() { 
            children = new Trie[26];
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) { 
            if(word == null || word.trim().length() == 0){ 
                return;
            }
            char first = word.charAt(0);
            int index = first - 'a';
            Trie child = children[index];
            if(child == null){ 
                child = new Trie();
                children[index] = child;
            }
    
            word = word.substring(1);
            if(word.length() > 0){ 
                child.insert(word);
            }else{ 
                child.is_end = true;
            }
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) { 
            if(word == null || word.trim().length() == 0){ 
                return true;
            }
            char first = word.charAt(0);
            int index = first - 'a';
            Trie child = children[index];
            if(child == null){ 
                return false;
            }
    
            word = word.substring(1);
            if(word.length() > 0){ 
                return child.search(word);
            }else{ 
                return child.is_end == true;
            }
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) { 
            if(prefix == null || prefix.trim().length() == 0){ 
                return true;
            }
            char first = prefix.charAt(0);
            int index = first - 'a';
            Trie child = children[index];
            if(child == null){ 
                return false;
            }
    
            prefix = prefix.substring(1);
            if(prefix.length() > 0){ 
                return child.startsWith(prefix);
            }else{ 
                return true;
            }
        }
    }
    
    /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

## 2.3 时间复杂度 ##

![在这里插入图片描述][2020121513154953.png]

*  insert  
    O(L)  
    因为在一个节点查找一个字符，直接用的数组下标查找，时间复杂度为O(1)。L表示目标单词长度。
 *  search  
    O(L)
 *  startsWith  
    O(L)

## 2.4 空间复杂度 ##

*  insert  
    O(L)  
    最坏情况。新插入的单词和之前的完全没有公共前缀，需要创建L个Trie对象
 *  search  
    O(L)  
    递归L次
 *  startsWith  
    O(L)  
    递归L次

# 2 循环版 #

## 2.1 思路 ##

遍历单词的每个字符，每次根据`char-'a'`从数组取child，取不到就说明不存在

## 2.2 代码 ##

class Trie { 
        private Trie[] children;
        private boolean is_end;
        /** Initialize your data structure here. */
        public Trie() { 
            children = new Trie[26];
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) { 
            Trie current = this;
            for(char c : word.toCharArray()){ 
                int index = c - 'a';
                Trie child = current.children[index];
                if(child == null){ 
                    child = new Trie();
                    current.children[index] = child;
                }
                current = child;
            }
            current.is_end = true;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) { 
            Trie current = this;
            for(char c : word.toCharArray()){ 
                current = current.children[c - 'a'];
                if(current == null){ 
                    return false;
                }
            }
            return current.is_end == true;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) { 
            Trie current = this;
            for(char c : prefix.toCharArray()){ 
                current = current.children[c - 'a'];
                if(current == null){ 
                    return false;
                }
            }
            return true;
        }
    }
    
    /** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200529153737494.png]

## 3.4 空间复杂度 ##

*  insert  
    O(L)  
    最坏情况。新插入的单词和之前的完全没有公共前缀，需要创建L个Trie对象
 *  search  
    O(1)
 *  startsWith  
    O(1)

[2020121513154953.png]: https://img-blog.csdnimg.cn/2020121513154953.png
[20200529153737494.png]: https://img-blog.csdnimg.cn/20200529153737494.png