描述

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

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

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

示例

示例 1：

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

示例 2：

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

提示

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 7
  • words[i] 仅由小写字母组成

解题思路

方法一：存储后缀

  • 由数据范围可知一个单词最多含有 7 个后缀，所以我们可以枚举单词所有的后缀。对于每个后缀，如果其存在 words 列表中，我们就将其从列表中删除。为了高效删除，我们将 words 用哈希集合来存储。

代码

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> good = new HashSet<String>(Arrays.asList(words));
        for (String word: words) {
            for (int k = 1; k < word.length(); ++k) {
                good.remove(word.substring(k));
            }
        }

        int ans = 0;
        for (String word: good) {
            ans += word.length() + 1;
        }
        return ans;
    }
}

方法二：字典树

  • 在插入之前需要先根据单词的长度由长到短排序，然后将字符串倒序插入
  • 如果是新单词的话编码长度增加新单词的长度+1，否则不变。

代码

class Solution {
    public int minimumLengthEncoding(String[] words) {
        int len = 0;
        Trie trie = new Trie();
        // 先对单词列表根据单词长度由长到短排序
        Arrays.sort(words, (s1, s2) -> s2.length() - s1.length());
        // 单词插入trie，返回该单词增加的编码长度
        for (String word: words) {
            len += trie.insert(word);
        }
        return len;
    }
}

// 定义tire
class Trie {

    TrieNode root;

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

    public int insert(String word) {
        TrieNode cur = root;
        boolean isNew = false;
        // 倒着插入单词
        for (int i = word.length() - 1; i >= 0; i--) {
            int c = word.charAt(i) - 'a';
            if (cur.children[c] == null) {
                isNew = true; // 是新单词
                cur.children[c] = new TrieNode();
            }
            cur = cur.children[c];
        }
        // 如果是新单词的话编码长度增加新单词的长度+1，否则不变。
        return isNew? word.length() + 1: 0;
    }
}

class TrieNode {
    char val;
    TrieNode[] children = new TrieNode[26];

    public TrieNode() {}
}

下面提供不排序的方法：
排序是为了防止出现先插入字典树的单词长度小于后面以这个单词为后缀的单词的长度的情况，因为这时多统计了前面插入的单词的长度。所以不排序的话，我们需要每次都检查以当前结点结尾的单词是否为一个后缀，如果是，需要从 res 中减去它的长度。

代码：

class Solution {
    public int minimumLengthEncoding(String[] words) {
        int res = 0;
        Trie root = new Trie();
        for (String word : words) {
            Trie cur = root;
            boolean flag = true; // 只有新单词才需要统计长度
            for(int i = word.length() - 1; i >= 0; i--) {
                int index = word.charAt(i) - 'a';
                if (cur.children[index] == null) {
                    cur.children[index] = new Trie();
                    flag = false;
                } else if (cur.children[index] != null && cur.children[index].str != null && i != 0) {
                    res -= cur.children[index].str.length() + 1; 
                    cur.children[index].str = null;
                }
                cur = cur.children[index];
            }
            if (!flag) {
                cur.str = word;
                res += word.length() + 1;
            }
        }
        return res;
    }
}
class Trie {
    Trie[] children;
    String str;
    Trie() {
        children = new Trie[26];
    } 
}