前缀树（Trie）构建与应用

发表于

这是我参与11月更文挑战的第6天，活动详情查看：2021最后一次更文挑战

1、前缀树介绍

  • 前缀树（Trie树），即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。
  • 典型应用是用于 统计 和 排序 大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
  • 优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
  • 以下介绍图源于网络

字典树.jpg

字典树1.jpg

2、前缀树应用（剑指 Offer 替换单词）

  • 在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。需要输出替换之后的句子。
  • 示例1
1
2
3
ini复制代码输入： dictionary = ["cat","bat","rat"], 
       sentence = "the cattle was rattled by the battery"
输出：            "the cat was rat by the bat"
  • 示例2
1
2
3
ini复制代码输入：dictionary = ["ac","ab"], 
      sentence = "it is abnormal that this solution is accepted"
输出：           "it is ab that this solution is ac"
  • 实现代码以及注释
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
ini复制代码class Solution {

    class TreeNode {               // 构建前缀树节点
        TreeNode[] kids;           // 指向的孩子节点
        boolean word = false;
        public TreeNode() {
            kids = new TreeNode[26];
        }
    }
    TreeNode root = new TreeNode();
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] dicts = dictionary.toArray(new String[dictionary.size()]);
        String[] words = sentence.split(" ");
        for (String s : dicts) {
            buildTree(s);            // 建立前缀树
        }

        StringBuilder sb = new StringBuilder();
        for (String s : words) {
            sb.append(find(s));  // 寻找符合的前缀单词
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    private void buildTree(String s) {
        char[] cs = s.toCharArray();
        TreeNode node = root;
        for (char c : cs) {
            if (node.kids[c - 'a'] == null) {
                node.kids[c - 'a'] = new TreeNode();  // 若是该节点为空，则为它分配一个孩子节点
            }
            node = node.kids[c - 'a'];                // 当前节点指向下一个目标节点
        }
        node.word = true;      // 标志着此处为前缀树单词结束位置
    }

    private String find(String s) {
        char[] cs = s.toCharArray();
        TreeNode node = root;
        int p = 0;
        for (char c : cs) {
            if (node.word == true) return s.substring(0,p);  // 前缀树结束单词最后一个字母，返回 s[0,p) 即可
            if (node.kids[c - 'a'] == null) return s;
            node = node.kids[c - 'a'];
            p++;
        }
        return s.substring(0,p);
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%