[数据结构与算法]【leetcode】最短的单词编码

一、题目描述

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

words.length == indices.length

助记字符串 s 以 ‘#’ 字符结尾

对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 ‘#’ 字符结束（但不包括 ‘#’）的 子字符串 恰好与 words[i] 相等

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

输入：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#”

二、代码思路

读懂题目：

1、 先读懂题目

题目就是讲，使用一种字符串浓缩手段，把一串字符串数组浓缩。

其实这样一想，反而是把字符串的公共部分提取，然后将公共部分和非公共部分组合在一起，而且并不是随便提取、随便组合，要考虑出能从字符串中截取出目标字符串。

这样的话，反而是有点难度，因为有多个字符，如何找相同的合并，如何保证合并出的字符串是最小的 ？ （其实就是后缀，没有那么复杂）

解题思路：

1、 是不是可以用贪心算法（贪心是对的，但是具体的实施是找后缀，并非是包含） ？

要求注记字符串长度最小，那么我们从短字符开始，依次找看哪个字符串包含该字符。（之所以从最小的开始比，就是应为贪心策略，小的更容易被其他字符串包含，从而保证注记符更短）

如果，存在字符串包含小字符串，那么这个小字符串可以删去。

如果存在一个长字符串和一个短字符串同时包含小字符串，那么我们应该选长字符串包含。（贪心先这样想）

如果存在已经包含小字符串的字符串也被其他字符串包含，那么该字符串也可以被删掉。

如果存在小字符串没被其他字符串包含，那么该小字符串就留下。

2、 使用hashMap解决问题

思路1：

我们可以枚举出一个单词的所有后缀。

如果这个单词的后缀正好是另一个单词，那么另一个单词就无需被编码，因为该单词已经包含另一个单词。

那么如何进行将后缀和已有单词进行比较呢 ？ 也可以理解为如何判断某一个后缀是这些单词中的一个呢 ？

也有两种方案：

1、 暴力求解，对于每个后缀 依次遍历words数据，比对是否和words数组中的单词相同。

2、 我们可以使用该后缀作为 key，然后从集合中找是否有相同的key，如此更节省事件啊，利用集合的特点。（集合中放的是words数组，只要某个单词的后缀key和words数组某个单词一致，那么该单词就可以被删掉）

3、使用后缀树解决问题

本质上是和第二种方法类似的。

三、 代码题解

package leetcode.lc20221008;

import java.util.Arrays;
import java.util.Comparator;

/*
 * @author lzy
 * @version 1.0
 * */
public class minumEncoding {
    public int minimumLengthEncoding(String[] words) {
        //读懂题目：
        //1、 先读懂题目
        //题目就是讲，使用一种字符串浓缩手段，把一串字符串数组浓缩。
        //其实这样一想，反而是把字符串的公共部分提取，然后将公共部分和非公共部分组合在一起
        //而且并不是随便提取、随便组合，要考虑出能从字符串中截取出目标字符串。
        //这样的话，反而是有点难度，因为有多个字符，如何找相同的合并，如何保证合并出的字符串是最小的？
        //解题思路：
        //1、 是不是可以用贪心算法 ？
        //要求注记字符串长度最小，那么我们从短字符开始，依次找看哪个字符串包含该字符。（之所以从最小的开始比，就是应为贪心策略，小的更容易被其他字符串包含，从而保证注记符更短）
        //如果，存在字符串包含小字符串，那么这个小字符串可以删去。
        //如果存在一个长字符串和一个短字符串同时包含小字符串，那么我们应该选长字符串包含。（贪心先这样想）
        //如果存在已经包含小字符串的字符串也被其他字符串包含，那么该字符串也可以被删掉。
        //如果存在小字符串没被其他字符串包含，那么该小字符串就留下。
        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        //表示返回结果的长度
        int res = 0;
        for (int i = 0; i < words.length; i++) {
            res += words[i].length();
            for (int j = i + 1; j < words.length; j++) {
                if (words[j].contains(words[i])) {
                    res -= words[i].length();
                    //如果还想要进一步获得slice数组，那么就需要一致比对，找到那个长度最长的数组，并标记位置。
                    break;
                }
            }
            //如果没有包含的情况，那么该字符串就需要留下来，res的长度需要加上该字符串长度
        }
        //返回编码数组的长度 + #号的个数
        return res + words.length - 1;
        //只能过13个点，剩下23个点逻辑错误，我也不知道咋整。
    }
}

HashMap

class Solution {
    public int minimumLengthEncoding(String[] words) {
        //思路1：
        //我们可以枚举出一个单词的所有后缀。
        //如果这个单词的后缀正好是另一个单词，那么另一个单词就无需被编码，因为该单词已经包含另一个单词。
        //那么如何进行将后缀和已有单词进行比较呢 ？ 也可以理解为如何判断某一个后缀是这些单词中的一个呢 ？
        //也有两种方案：
        //1、 暴力求解，对于每个后缀 依次遍历words数据，比对是否和words数组中的单词相同
        //2、 我们可以使用该后缀作为 key，然后从集合中找是否有相同的key，如此更节省事件啊，利用集合的特点。
        HashSet<String> setWords = new HashSet<>(Arrays.asList(words));
        for (String str : words) {
            //枚举该单词的所有后缀，并且将后缀放入集合中比较，观察是否有单词与这个后缀一摸一样。
            //如果这个单词和后缀一摸一样，那么就不用解码这个单词。
            for (int i = 1; i < str.length(); i++) {
                //枚举后缀
                String suffix = str.substring(i);
                setWords.remove(suffix);
            }
        }
        int res = 0;
        //for each走的还是集合的迭代器： 使用 hasNext 和 next 判断是否有元素。
        for (String str : setWords) {
            res += str.length() + 1;
        }
        return res;
    }
}

前缀树：

解释看官方题解

class Solution {
    public int minimumLengthEncoding(String[] words) {
        TrieNode trie = new TrieNode();
        Map<TrieNode, Integer> nodes = new HashMap<TrieNode, Integer>();

        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            TrieNode cur = trie;
            for (int j = word.length() - 1; j >= 0; --j) {
                cur = cur.get(word.charAt(j));
            }
            nodes.put(cur, i);
        }

        int ans = 0;
        for (TrieNode node: nodes.keySet()) {
            if (node.count == 0) {
                ans += words[nodes.get(node)].length() + 1;
            }
        }
        return ans;

    }
}

class TrieNode {
    TrieNode[] children;
    int count;

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

    public TrieNode get(char c) {
        if (children[c - 'a'] == null) {
            children[c - 'a'] = new TrieNode();
            count++;
        }
        return children[c - 'a'];
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/iSwD2y/solution/zui-duan-de-dan-ci-bian-ma-by-leetcode-s-qjxw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。