Formatted question description: https://leetcode.ca/all/820.html

820. Short Encoding of Words

Level

Medium

Description

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. 1 <= words.length <= 2000.
  2. 1 <= words[i].length <= 7.
  3. Each word has only lowercase letters.

Solution

If a word is a postfix of another word, then only the longer word needs to be encoded, since the shorter word is contained in the longer word and both words have the same last letter. Therefore, the solution is to find all the words that are not postfixes of any other words.

Use a trie to solve this. Since a trie stores prefixes and this problem uses postfixes, for each word in words, store the letters in the trie in reversing order.

After all words are stored in the trie, do breadth first search on the trie and find all the leaf nodes. Suppose the root node that does not contain any letter is at depth 0, then for each leaf node, if it is at depth d, then the word has length d, and a "#" character is added after the word, so add d + 1 to the total length. Finally, return the total length.

class Solution {
    public int minimumLengthEncoding(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            int length = word.length();
            for (int i = length - 1; i >= 0; i--) {
                char letter = word.charAt(i);
                int index = letter - 'a';
                if (node.next[index] == null)
                    node.next[index] = new TrieNode();
                node = node.next[index];
            }
            node.wordEnd = true;
        }
        int totalLength = 0;
        int depth = 0;
        Queue<TrieNode> queue = new LinkedList<TrieNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TrieNode node = queue.poll();
                TrieNode[] next = node.next;
                int childrenCount = 0;
                for (TrieNode child : next) {
                    if (child != null) {
                        queue.offer(child);
                        childrenCount++;
                    }
                }
                if (childrenCount == 0)
                    totalLength += depth + 1;
            }
            depth++;
        }
        return totalLength;
    }
}

class TrieNode {
    boolean wordEnd;
    TrieNode[] next;

    public TrieNode() {
        wordEnd = false;
        next = new TrieNode[26];
    }
}

All Problems

All Solutions