[数据结构与算法]数据结构 之 前缀树

前言

前缀树是一种利于高效地存储和检索字符串数据集中的键，适合用于表示有基础变量复合出来的复杂变量，如26个字符复合出来的单词，实现快速搜索和插入，以及前缀查询。

一、案例

二、题解

package com.xhu.offer.offerII;

//实现前缀树
public class Trie {
    TreeNode root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new TreeNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        char[] chs = word.toCharArray();
        TreeNode p = root;

        for (char ch : chs) {
            int idx = ch - 'a';
            TreeNode n = p.next[idx];

            if (n == null) p.next[idx] = new TreeNode();

            p = n;
        }
        p.isEnd = true;
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        char[] chs = word.toCharArray();
        TreeNode p = root;
        for (char ch : chs) {
            int idx = ch - 'a';
            TreeNode n = p.next[idx];
            if (n == null) return false;

            p = n;
        }
        return p.isEnd;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        char[] chs = prefix.toCharArray();
        TreeNode p = root;
        for (char ch : chs) {
            int idx = ch - 'a';
            TreeNode n = p.next[idx];
            if (n == null) return false;

            p = n;
        }
        return true;
    }

    //只有小写字母，定义前缀树的数据结构
    public class TreeNode {
        boolean isEnd;

        TreeNode[] next;

        public TreeNode() {
            next = new TreeNode[26];
        }
    }
}

总结

1）第一次见前缀树结构，适用于固定的单一变量复合出复杂变量问题。

参考文献

[1] LeetCode 原题
[2] LeetCode 用户评论

附录

1、替换单词

package com.xhu.offer.offerII;

import java.util.Iterator;
import java.util.List;

//替换单词
public class ReplaceWords {
    //构建词根树
    TreeNode root = new TreeNode();

    public String replaceWords(List<String> dictionary, String sentence) {
        buildTrie(dictionary);
        //替换单词
        StringBuilder sb = new StringBuilder();
        String[] strs = sentence.split(" ");
        for (String str : strs) {
            char[] chs = str.toCharArray();

            TreeNode p = root;
            int count = 0;
            for (char ch : chs) {
                int idx = ch - 'a';
                TreeNode n = p.next[idx];
                if (n == null || p.isEnd) break;
                count++;
                p = p.next[idx];
            }
            sb.append(p.isEnd ? str.substring(0, count) : str).append(" ");
        }
        return sb.toString().trim();
    }


    private void buildTrie(List<String> dic) {
        Iterator<String> iterator = dic.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            char[] chs = s.toCharArray();
            TreeNode p = root;
            for (char ch : chs) {
                int idx = ch - 'a';
                TreeNode n = p.next[idx];
                if (n == null) p.next[idx] = new TreeNode();
                p = p.next[idx];
            }
            p.isEnd = true;
        }
    }

    public class TreeNode {
        boolean isEnd;
        TreeNode[] next = new TreeNode[26];
    }

}

2、神奇的字典

package com.xhu.offer.offerII;

import java.util.ArrayList;
import java.util.List;

//神奇的字典
public class MagicDictionary {
    /**
     * Initialize your data structure here.
     */
    public MagicDictionary() {

    }

    /**
     * 构造前缀树
     *
     * @param dictionary 前缀树构造所需单词
     */
    public void buildDict(String[] dictionary) {
        for (String s : dictionary) {
            char[] chs = s.toCharArray();
            TreeNode p = root;

            for (char ch : chs) {
                int idx = ch - 'a';

                if (p.next[idx] == null) p.next[idx] = new TreeNode();

                p = p.next[idx];
            }
            p.isEnd = true;
        }
    }

    TreeNode root = new TreeNode();

    public boolean search(String searchWord) {
        return recursion(root, searchWord, 0, 0);
    }

    /**
     * DFS
     *
     * @param root       表示上一次比较时所用节点，即父节点，递归口通过判断父节点是否为end节点来确定是否完全匹配。
     * @param searchWord 表示需要去DFS匹配的字符串
     * @param i          该比searchWord的第几个字符了
     * @param count      表示前面已经有几个字符不同了
     * @return 只要匹配成功一次就返回true，即成功匹配，否则false，for中的flag为false表示继续DFS，for外的false表示DFS完也匹配不成功
     */
    private boolean recursion(TreeNode root, String searchWord, int i, int count) {
        if (count > 1 || root == null) return false;
        if (i == searchWord.length()) {
            if (root.isEnd && count == 1) return true;
            else return false;
        }
        for (int j = 0; j < 26; j++) {
            boolean flag = false;
            int idx = searchWord.charAt(i) - 'a';

            if (idx != j) flag = recursion(root.next[j], searchWord, i + 1, count + 1);
            else flag = recursion(root.next[j], searchWord, i + 1, count);
            if (flag) return true;
        }
        return false;
    }


    public class TreeNode {
        boolean isEnd;
        TreeNode[] next = new TreeNode[26];
    }
}

//使用list，找同等长度的字符串拿去作比较，修改修改一次两者相等，则true，否则false。
//这里判断是否修改一次相等，就对比有多少字符不相等即可。
class MagicDictionary2 {
    List<String> cache = new ArrayList<>();

    /**
     * Initialize your data structure here.
     */
    public MagicDictionary2() {

    }

    public void buildDict(String[] dictionary) {
        for (String s : dictionary) cache.add(s);
    }

    public boolean search(String searchWord) {
        int size = cache.size();

        for (String s : cache) {
            if (s.length() != searchWord.length()) continue;
            if (find(s, searchWord)) return true;
        }
        return false;
    }

    //注：只修改一次，直接比较字符不等的时候有多少，不用递归+for那么麻烦。
    private boolean find(String s, String searchWord) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != searchWord.charAt(i)) count++;
            if (count > 1) return false;
        }

        return count == 1;
    }

}

3、最短单词编码之逆前缀树

掌握好前缀树的各个细节，才能举一反三，采用逆前缀树来解决最短单词编码。

package com.xhu.offer.offerII;

//最短的单词编码
public class MinimumLengthEncoding {
    //倒装的前缀树即可，然后统计每条路径长度之和 + 路径条数(需要多少#)
    public int minimumLengthEncoding(String[] words) {
        //建树
        buildTree(words);
        //统计路径
        return countPath(root)[0];
    }


    private int[] countPath(TreeNode root) {

        if (root.next == null) {
            return new int[]{1, 1};
        }
        int res = 0, count = 0;
        for (int i = 0; i < 26; i++) {
            if (root.next[i] != null) {
                int[] r = countPath(root.next[i]);
                count += r[1];
                res += r[0];
            }
        }
        return new int[]{res + count, count};
    }

    TreeNode root = new TreeNode();

    private void buildTree(String[] words) {
        for (String word : words) {
            char[] chs = word.toCharArray();
            TreeNode p = root;
            for (int i = chs.length - 1; i >= 0; i--) {
                int idx = chs[i] - 'a';
                if (p.next == null) p.next = new TreeNode[26];
                if (p.next[idx] == null) p.next[idx] = new TreeNode();
                p = p.next[idx];
            }
        }
    }

    public class TreeNode {
        TreeNode[] next;
    }
}

4、单词之和

package com.xhu.offer.offerII;

//单词之和
public class MapSum {
    //前缀树

    /**
     * Initialize your data structure here.
     */
    public MapSum() {

    }

    TreeNode root = new TreeNode();

    public void insert(String key, int val) {
        char[] chs = key.toCharArray();
        TreeNode p = root;

        for (char ch : chs) {
            int idx = ch - 'a';

            if (p.next == null) p.next = new TreeNode[26];
            if (p.next[idx] == null) p.next[idx] = new TreeNode();

            p = p.next[idx];
        }
        p.isEnd = true;
        p.val = val;
    }


    public int sum(String prefix) {
        char[] chs = prefix.toCharArray();

        TreeNode p = root;
        for (char ch : chs) {
            int idx = ch - 'a';

            if (p.next == null || p.next[idx] == null) return 0;

            p = p.next[idx];
        }
        int[] total = new int[]{0};
        order(p, total);

        return total[0];
    }

    private void order(TreeNode p, int[] total) {
        if (p.isEnd) {
            total[0] += p.val;
        }
        if (p.next == null) return;

        for (int i = 0; i < 26; i++) {
            if (p.next[i] != null) order(p.next[i], total);
        }
    }

    public class TreeNode {
        boolean isEnd;
        int val;
        TreeNode[] next;
    }
}

5、最大的异或

package com.xhu.offer.offerII;


//最大的异或
public class FindMaximumXOR {
    TreeNode root = new TreeNode();

    public int findMaximumXOR(int[] nums) {
        //建树
        buildTree(nums);
        //寻找最大解
        int res = 0;
        for (int num : nums) {
            int t = find(num);
            res = res < t ? t : res;
        }
        return res;
    }


    private int find(int num) {
        int count = 30;
        TreeNode p = root;
        int res = 0;
        while (count >= 0) {
            int m = num >>> count & 1;
            boolean f1 = m == 1 && p.right != null, f2 = m == 0 && p.left != null;

            if (f1 || f2) res |= 1 << count;

            if (p.right != null && (m == 1 || p.left == null)) p = p.right;
            else p = p.left;
            count--;
        }
        return res;
    }

    private void buildTree(int[] nums) {
        for (int num : nums) {
            int count = 30;
            TreeNode p = root;

            while (count >= 0) {
                int m = num >>> count-- & 1;
                boolean f1 = m == 1 && p.left == null, f2 = m == 0 && p.right == null;
                if (f1) p.left = new TreeNode();
                if (f2) p.right = new TreeNode();

                p = m == 1 ? p.left : p.right;
            }
        }
    }

    public class TreeNode {
        TreeNode left;//1
        TreeNode right;//0
    }
}