题目

给定一个单词列表，我们将这个列表编码成一个索引字符串 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] 。

分析

1. 最初想法
   首先匹配子串会让人想到 Trie 树，但本题题意是匹配后缀，所以会想到把单词翻转，构造前缀树条件，生成前缀树，计算每一个子节点到父节点的距离（ # 相当于根节点，所以需要算上根节点的个数 1 ）。
2. 在此基础上的思考
   既然每个节点的共享部分都需要反复计算，那么是不是可以理解为，其实过滤掉不用计算的是整个单词能匹配到其他单词的情况（包含关系，而不是半包含关系），那么只需要遍历每个单词，过滤掉当前单词的所有后缀以独立单词存在的情况，再对剩下的单词长度求和（别忘了根节点）即可。

题解

/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function (words) {
    let set = new Set(words);
    for (let word of set) {
        for (let i = 1; i < word.length; i++) {
            let temp = word.slice(i);
            set.has(temp) && set.delete(temp);
        }
    }
    let res = [...set].reduce((acc,cur)=>{
        return acc+cur.length+1;
    },0)
    return res;
};