zhang

第10章 前缀树

Mr.Zhang算法前缀树大约 8 分钟

第10章 前缀树

剑指offerⅡ62：实现前缀树

Trieopen in new window（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
class Trie {
    private TrieNode root;

    class TrieNode {
        TrieNode[] children;
        boolean isWord;

        public TrieNode() {
            children = new TrieNode[26];
        }
    }

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

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                node.children[ch - 'a'] = new TrieNode();
            }
            node = node.children[ch - 'a'];
        }
        node.isWord = true;
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if(node.children[ch - 'a'] == null){
                return false;
            }
            node = node.children[ch - 'a'];
        }
        return node.isWord;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if(node.children[ch - 'a'] == null){
                return false;
            }
            node = node.children[ch - 'a'];
        }
        return true;
    }
}

前缀树的应用

剑指offerⅡ63：替换单词

在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

需要输出替换之后的句子。

示例 1：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 2：

输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
输出："a a b c"

示例 3：

输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
输出："a a a a a a a a bbb baba a"

示例 4：

输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

示例 5：

输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
输出："it is ab that this solution is ac"

提示：

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] 仅由小写字母组成。
  • 1 <= sentence.length <= 10^6
  • sentence 仅由小写字母和空格组成。
  • sentence 中单词的总量在范围 [1, 1000] 内。
  • sentence 中每个单词的长度在范围 [1, 1000] 内。
  • sentence 中单词之间由一个空格隔开。
  • sentence 没有前导或尾随空格。
class Solution {
    TrieNode root;

    class TrieNode {
        TrieNode[] children;
        boolean isWord;

        TrieNode() {
            children = new TrieNode[26];
        }
    }

    private void buildTrie(List<String> dictionary) {
        root = new TrieNode();//don't forget this statement
        for (String dic : dictionary) {
            TrieNode node = root;
            for (char ch : dic.toCharArray()) {
                if (node.children[ch - 'a'] == null) {
                    node.children[ch - 'a'] = new TrieNode();
                }
                node = node.children[ch - 'a'];
            }
            node.isWord = true;
        }
    }

    private String findPrefix(String word) {
        StringBuilder sb = new StringBuilder();
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.isWord || node.children[ch - 'a'] == null) {
                break;
            }
            sb.append(ch);
            node = node.children[ch - 'a'];
        }
        return node.isWord ? sb.toString() : "";//如果isWord为true，代表找到。
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        buildTrie(dictionary);

        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            String prefix = findPrefix(words[i]);
            if (!prefix.isEmpty()) {
                words[i] = prefix;
            }
        }
        return String.join(" ", words);
    }
}

剑指offerⅡ64：神奇的字典

设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。

实现 MagicDictionary 类：

  • MagicDictionary() 初始化对象
  • void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
  • bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

示例：

输入
inputs = ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
inputs = [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
输出
[null, null, false, true, false, false]

分析：将每个完整的单词保存到哈希表中并不能解决该问题。这是因为字符串的哈希值是由整个字符串决定的，修改字符串中任意一个字符之后，字符串的哈希值和原来字符串的哈希值没有任何关系。因此，如果用哈希表保存字典中所有的单词，就没有办法找出只修改一个字符的字符串。

class MagicDictionary {
    TrieNode root;

    class TrieNode {
        TrieNode[] children;
        boolean isWord;

        TrieNode() {
            children = new TrieNode[26];
        }
    }

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

    public void buildDict(String[] dictionary) {
        for (String dic : dictionary) {
            TrieNode node = root;
            for (char ch : dic.toCharArray()) {
                if (node.children[ch - 'a'] == null) {
                    node.children[ch - 'a'] = new TrieNode();
                }
                node = node.children[ch - 'a'];
            }
            node.isWord = true;
        }
    }

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

    private boolean dfs(TrieNode root, String word, int i, int edit) {
        if (root == null) {
            return false;
        }
        if (i == word.length() && root.isWord && edit == 1) {
            return true;
        }
        if (i < word.length() && edit <= 1) {
            boolean found = false;
            for (int j = 0; j < 26 && !found; j++) {
                //whether next is to be exchanged
                int next = (j == word.charAt(i) - 'a') ? edit : edit + 1;
                found = dfs(root.children[j], word, i + 1, next);
            }
            return found;
        }
        return false;
    }
}

剑指offerⅡ65：最短的单词编码

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

  • words.length == indices.length
  • 助记字符串 s 以 '#' 字符结尾
  • 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等

给定一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

示例 1：

输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"

示例 2：

输入：words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0] 。

class Solution {
    TrieNode root;
    class TrieNode{
        TrieNode[] children;
        boolean isWord;
        TrieNode(){
            children = new TrieNode[26];
        }
    }

    private void buildTrie(String[] words){
        root = new TrieNode();
        for(String word : words){
            TrieNode node = root;
            for(int i = word.length() - 1; i >=0; i--){
                if(node.children[word.charAt(i) - 'a'] == null){
                    node.children[word.charAt(i) - 'a'] = new TrieNode();
                }
                node = node.children[word.charAt(i) - 'a'];
            }
            node.isWord = true;
        }
    }

    public int minimumLengthEncoding(String[] words) {
        buildTrie(words);
        int[] total = new int[]{0};
        dfs(root, 1, total);
        return total[0];
    }

    private void dfs(TrieNode root, int length, int[] total){
        boolean isLeaf = true;
        for(TrieNode child : root.children){
            if(child != null){
                isLeaf = false;
                dfs(child, length + 1, total);
            }
        }
        if(isLeaf){
            total[0] += length;
        }
    }
}

剑指offerⅡ66：单词之和

实现一个 MapSum 类，支持两个方法，insert 和 sum：

  • MapSum() 初始化 MapSum 对象
  • void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
  • int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

示例：

输入：
inputs = ["MapSum", "insert", "sum", "insert", "sum"]
inputs = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：
[null, null, 3, null, 5]

提示：

  • 1 <= key.length, prefix.length <= 50
  • key 和 prefix 仅由小写英文字母组成
  • 1 <= val <= 1000
  • 最多调用 50 次 insert 和 sum
class MapSum {
    TrieNode root;

    class TrieNode {
        TrieNode[] children;
        int val;//初始化默认为0

        TrieNode() {
            children = new TrieNode[26];
        }
    }

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

    public void insert(String key, int val) {
        TrieNode node = root;
        for (char ch : key.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                node.children[ch - 'a'] = new TrieNode();
            }
            node = node.children[ch - 'a'];
        }
        node.val = val;
    }

    public int sum(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (node.children[ch - 'a'] == null) {
                return 0;
            } else {
                node = node.children[ch - 'a'];
            }
        }
        int[] ans = {0};
        /**
         *         BFS算法:将ans的类型改成int
         *         Deque <TrieNode> queue = new LinkedList<>();
         *         queue.offer(node);
         *         while(!queue.isEmpty()){
         *             TrieNode temp = queue.pollFirst();
         *             ans += temp.val;
         *             for(int i = 0; i < 26; i++){
         *                 if(temp.children[i] != null){
         *                     queue.offer(temp.children[i]);
         *                 }
         *             }
         *         }
         */
        dfs(node, ans);
        return ans[0];
    }

    private void dfs(TrieNode node, int[] ans) {
        if (node == null) {
            return;
        }
        ans[0] += node.val;
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                dfs(node.children[i], ans);
            }
        }
    }
}

剑指offerⅡ67：最大的异或

给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

示例 1：

输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：

输入：nums = [0]
输出：0

示例 3：

输入：nums = [2,4]
输出：6

示例 4：

输入：nums = [8,10,2]
输出：10

示例 5：

输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：

  • 1 <= nums.length <= 2 * 104
  • 0 <= nums[i] <= 231 - 1

**进阶：**你可以在 O(n) 的时间解决这个问题吗？

class Solution {
    TrieNode root;

    class TrieNode {
        TrieNode[] children;

        TrieNode() {
            children = new TrieNode[2];
        }
    }

    public int findMaximumXOR(int[] nums) {
        buildTrie(nums);
        int ans = 0;
        for (int num : nums) {
            int sum = 0;
            TrieNode node = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (node.children[1 - bit] != null) {
                    sum = sum * 2 + 1;
                    node = node.children[1 - bit];
                } else {
                    sum = sum * 2;
                    node = node.children[bit];
                }
            }
            ans = Math.max(ans, sum);
        }

        return ans;
    }

    private void buildTrie(int[] nums) {
        root = new TrieNode();
        for (int num : nums) {
            TrieNode node = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;//从左到右获取num的每一位
                if (node.children[bit] == null) {
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
            }
        }
    }
}
Loading...
很高兴见到你
Copyright © 2022 Mr.Zhang