系列文章

【英雄哥六月集训】第 01天:数组

【英雄哥六月集训】第 02天:字符串

【英雄哥六月集训】第 03天:排序

【英雄哥六月集训】第 04天:贪心

【英雄哥六月集训】第 05天: 双指针

【英雄哥六月集训】第 06天:滑动窗口

【英雄哥六月集训】第 07天:哈希

【英雄哥六月集训】第 08天:前缀和

【英雄哥六月集训】第 09天:二分查找

【英雄哥六月集训】第 10天: 位运算

【英雄哥六月集训】第 11天: 矩阵

【英雄哥六月集训】第 12天: 链表

【英雄哥六月集训】第 13天: 双向链表

【英雄哥六月集训】第 14天: 栈

【英雄哥六月集训】第 15天: 二叉树

【英雄哥六月集训】第 16天: 队列

【英雄哥六月集训】第 17天: 广度优先搜索

【英雄哥六月集训】第 18天: 树

【英雄哥六月集训】第 19天: 二叉树

【英雄哥六月集训】第 20天: 二叉搜索树

【英雄哥六月集训】第 21天: 堆(优先队列)

【英雄哥六月集训】第 22天: 有序集合

【英雄哥六月集训】第 23天: 字典树

---

字典树

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

一、 连接词

472. 连接词

class Solution {
    class Trie{
        Trie[] children;
        boolean isEnd;
        public Trie(){
            children = new Trie[26];
            isEnd = false;
        }
    }
    Trie trie= new Trie();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> ans = new ArrayList<String>();
        Arrays.sort(words,(a,b)->a.length()-b.length());
        for(int i=0; i< words.length; i++){
            String word = words[i];
            if(word.length()==0){
                continue;
            }
            boolean[] visited = new boolean[word.length()];
            if(dfs(word,0,visited)){
                ans.add(word);
            } else {
                insert(word);
            }
        }
        return ans;

    }

    public boolean dfs(String word,int start,boolean[] visited){
        if(word.length() == start){
            return true;
        }
        if(visited[start]){
            return false;
        }
        visited[start] = true;
        Trie node = trie;
        for( int i=start; i<word.length(); i++){
            char ch = word.charAt(i);
            int index = ch - 'a';
            node = node.children[index];
            if(node == null){
                return false;
            }
            if(node.isEnd){
                if(dfs(word,i+1,visited)){
                    return true;
                }
            }
        }
        return false;
    }
    public void insert(String word){
        Trie node = trie;
        for(int i = 0;i<word.length();i++){
            char ch=word.charAt(i);
            int index = ch -'a';
            if(node.children[index]==null){
                node.children[index]= new Trie();
            }
            node = node.children[index];
        }
        node.isEnd=true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

---

二、 最长单词

面试题 17.15. 最长单词

class Solution {
    class Trie{
        Trie[] children;
        boolean isEnd;
        public Trie(){
            children = new Trie[26];
            isEnd = false;
        }
    }
    Trie trie= new Trie();

    public boolean dfs(String word,int start){
        
        
        Trie node = trie;
        if(word.length() == start){
            return true;
        }
        
        for(int i=start;i<word.length();i++){
            int c=word.charAt(i)-'a';
            node=node.children[c];
            if(node == null) return false;
            if(node.isEnd){
                if(dfs(word,i+1)){
                    return true;
                }
            }
        }
        return false;
    }
    public void insert(String word){
        Trie node = trie;
        for(int i = 0;i<word.length();i++){
            char ch=word.charAt(i);
            int index = ch -'a';
            if(node.children[index]==null){
                node.children[index]= new Trie();
            }
            node = node.children[index];
        }
        node.isEnd=true;
    }
    public String longestWord(String[] words) {
        String ret="";
        Arrays.sort(words,(o1,o2)->o1.length()-o2.length());
        for(String word:words){
            if(word.length()==0) continue;
            if(dfs(word,0)){
                if(ret.length()<word.length()){
                    ret=word;
                } else if(ret.length()==word.length()){
                    if(ret.compareTo(word)>0){
                        ret = word;
                    }
                }
            }
            else{
                insert(word);
            }
        }

        
        return ret;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

总结

getOrDefault(Object key, V defaultValue)
意思就是当Map集合中有这个key时，就使用这个key对应的value值，如果没有就使用默认值defaultValue