Welcome to Subscribe On Youtube

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];
    }
}

  • // OJ: https://leetcode.com/problems/short-encoding-of-words/
// Time: O(NlogN * W)
// Space: O(W)
class Solution {
public:
    int minimumLengthEncoding(vector<string>& A) {
        string prev = "";
        int ans = 0;
        for (auto &s : A) reverse(begin(s), end(s));
        sort(begin(A), end(A));
        for (auto &s : A) {
            if (prev != "" && (s.size() < prev.size() || s.substr(0, prev.size()) != prev)) { // the current string can't cover the previous string, must start a new segment.
                ans += 1 + prev.size(); // close the previous segment.
            }
            prev = s;
        }
        return ans + 1 + prev.size();
    }
};

  • class Trie:
    def __init__(self) -> None:
        self.children = [None] * 26


class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        root = Trie()
        for w in words:
            cur = root
            for i in range(len(w) - 1, -1, -1):
                idx = ord(w[i]) - ord('a')
                if cur.children[idx] == None:
                    cur.children[idx] = Trie()
                cur = cur.children[idx]
        return self.dfs(root, 1)

    def dfs(self, cur: Trie, l: int) -> int:
        isLeaf, ans = True, 0
        for i in range(26):
            if cur.children[i] != None:
                isLeaf = False
                ans += self.dfs(cur.children[i], l + 1)
        if isLeaf:
            ans += l
        return ans

############
3
class Solution:
    def minimumLengthEncoding(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        words = sorted([word[::-1] for word in set(words)])
        last = ""
        ans = 0
        for word in words + [""]:
            if not word.startswith(last):
                ans += len(last) + 1
            last = word
        return ans

  • type trie struct {
	children [26]*trie
}

func minimumLengthEncoding(words []string) int {
	root := new(trie)
	for _, w := range words {
		cur := root
		for i := len(w) - 1; i >= 0; i-- {
			if cur.children[w[i]-'a'] == nil {
				cur.children[w[i]-'a'] = new(trie)
			}
			cur = cur.children[w[i]-'a']
		}
	}
	return dfs(root, 1)
}

func dfs(cur *trie, l int) int {
	isLeaf, ans := true, 0
	for i := 0; i < 26; i++ {
		if cur.children[i] != nil {
			isLeaf = false
			ans += dfs(cur.children[i], l+1)
		}
	}
	if isLeaf {
		ans += l
	}
	return ans
}

All Problems

All Solutions