LeetCode.820.Short Encoding of Words 单词的压缩编码

题目描述

820 Short Encoding of Words
https://leetcode-cn.com/problems/short-encoding-of-words/

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is [“time”, “me”, “bell”], we can write it as S = “time#bell#” and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:
1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

---

解题过程

暴力方法

遍历字符串数组并加入已编码的集合s，对于当前word：
如果s中存在以word为结尾的，说明word可以用已有的编码，跳过。
如果word以s中某个字符串为结尾，则用word替换s中的该字符串。
如果以上两种情况都没有，把word加入集合s

时间复杂度 O(l*n^2) ，其中n是数组长度，l是最大单词的长度
空间复杂度 O(ln)

private static class SolutionV2020 {
    public int minimumLengthEncoding(String[] words) {
        if (null == words || words.length == 0) {
            return 0;
        }
        List<String> list = new LinkedList<>();
        for (String word : words) {
            boolean exist = false;
            for (ListIterator<String> iterator = list.listIterator(); iterator.hasNext();) {
                String encodeStr = iterator.next();
                if (encodeStr.endsWith(word)) {
                    exist = true;
                    break;
                } else if (word.endsWith(encodeStr)) {
                    iterator.set(word);
                    exist = true;
                    break;
                }
            }
            if (!exist) {
                list.add(word);
            }
        }
        int count = 0;
        for (String s : list) {
            count += s.length() + 1;
        }
        return count;
    }
}

字典树/Trie树

private static class OfficeSolution {
    private static class TrieNode {
        public TrieNode[] children;
        public int count;
        public 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'];
        }
    }

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

        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;

    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_820_ShortEncodingOfWords.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_820_ShortEncodingOfWords.java

---