没事儿刷刷算法题——字典树的应用

SET技术干货 2021-10-17

677

一、概念

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

二、特点

根节点不包含字符，除根节点外每一个节点都只包含一个字符；
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
每个节点的所有子节点包含的字符都不相同。

三、常见操作

查找、插入和删除（很少用到）。

四、实现

代码如下，这段代码实现了字典树的insert以及根据前缀匹配所有字符串的方法。

public class Trie {


    private TrieNode root;


    public Trie(){
        root = new TrieNode();
    }


    public void insert(String str){
        if(str==null||str.length()==0){
            return;
        }
        TrieNode node = root;
        char[] allChars = str.toCharArray();
        for(int i=0; i<allChars.length; i++){
            Character character = new Character(allChars[i]);
            if (!node.children.containsKey(character)){
                node.children.put(character, new TrieNode(character));
            }
            node = node.children.get(character);
        }
        node.isEnd = true;
    }


    public List<String> matchPrefix(String prefix){
        List<String> result = new ArrayList<String>();
        if(prefix==null||prefix.length()==0){
            return result;
        }
        char[] allChars = prefix.toCharArray();
        TrieNode node = root;
        for(int i=0; i<allChars.length; i++){
            Character character = new Character(allChars[i]);
            if(!node.children.containsKey(character)){
                return result;
            }else{
                node = node.children.get(character);
            }
        }
        preTraverse(node, prefix, result);
        return result;
    }


    private void preTraverse(TrieNode node, String prefix, List<String> result){
        if(!node.children.isEmpty()){
            for (Map.Entry<Character, TrieNode> entry: node.children.entrySet()){
                if (entry.getValue().isEnd){
                    result.add(prefix+entry.getKey().toString());
                }
                preTraverse(entry.getValue(), prefix+entry.getKey().toString(), result);
            }
        }
    }


    private class TrieNode {


        private Map<Character, TrieNode> children;


        private boolean isEnd;


        private Character character;


        TrieNode(){
            children = new HashMap<Character, TrieNode>();
            isEnd = false;
        }


        TrieNode(Character character){
            children = new HashMap<Character, TrieNode>();
            isEnd = false;
            this.character = character;
        }
    }
}

我们通过一段代码测试一下：

public class MainApp {


    public static void main(String[] argv){
        ArrayList<String> strs = new ArrayList<String>();
        strs.add("我爱学习");
        strs.add("我爱学");
        strs.add("我爱学JAVA");
        strs.add("我不爱学习");
        strs.add("小明也爱学习");
        strs.add("我爱Python");


        Trie trie = new Trie();
        for(String s: strs){
            trie.insert(s);
        }
        String prefix = "我爱";
        List<String> res = trie.matchPrefix(prefix);
        System.out.println(res);
    }
}

执行后输出：[我爱Python, 我爱学, 我爱学习, 我爱学JAVA]

五、应用

给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。

对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。

那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

示例：

输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5]

通过分析，我们可以看出，这道题目标就是保留所有不是其他单词后缀的单词，最后的结果就是这些单词长度加一的总和（因为每个单词编码后后面还需要跟一个 # 符号）。很明显这里需要使用字典表。代码如下：

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        HashMap<TrieNode, Integer> nodes = new HashMap<TrieNode,Integer>();
        
        for(int k=0; k<words.length; k++){
            String s = words[k];
            TrieNode node = trie.insert(s);
            if(node!=null){
                nodes.put(node, k);    
            }
        }
        int res = 0;
        for(TrieNode n: nodes.keySet()){
            if(n.children.isEmpty()){
                res += words[nodes.get(n)].length()+1;
            }
        }
        return res;
    }
}


class Trie {
    TrieNode root;
    Trie(){
        root = new TrieNode();
    }
    TrieNode insert(String str){
        if(str==null||str.length()==0){
            return null;
        }
        TrieNode node = root;
        char[] allChars = str.toCharArray();
        for(int i=allChars.length-1; i>=0; i--){
            Character character = new Character(allChars[i]);
            if (!node.children.containsKey(character)){
                node.children.put(character, new TrieNode(character));
            }
            node = node.children.get(character);
        }
        node.isEnd = true;
        return node;
    }
}


class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEnd;
    Character character;
    TrieNode(){
        children = new HashMap<Character, TrieNode>();
        isEnd = false;
    }
    TrieNode(Character character){
        children = new HashMap<Character, TrieNode>();
        isEnd = false;
        this.character = character;
    }
}

PS：这里为了方便最后的字符串统计，所以对本文前面提供的字典表代码略作修改，但是整体思路是一样的。

数据库

文章转载自SET技术干货，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

没事儿刷刷算法题——字典树的应用

评论