820. Short Encoding of Words

Problem Description

The given problem is about finding the shortest reference string that can encode an array of words such that:

• words.length == indices.length, where indices is an array of indices.
• The reference string s must end with the character '#'.
• For each index indices[i], the substring of s starting from indices[i] and ending before the next '#' should be exactly words[i].

The goal is to return the minimum length of such a reference string s that fulfills the above conditions.

Intuition

In order to encode the words array with the shortest reference string, we have to look for opportunities to overlap words. If a word is a suffix of another, we can encode both with the longer word in the reference string. For example, if "time" is in the array, then encoding "me" doesn't require extra space; it is the last two letters of "time."

The solution uses a Trie structure, as it is a natural fit for dealing with prefixes and suffixes. A Trie is an ordered tree structure, which is used to store a dynamic set or associative array where the keys are usually strings. Instead of storing whole words in each node, we store characters, and each path down the tree represents a word.

1. We first reverse each word and insert it into the Trie. We reverse the words because we want to group words by suffixes (the end of the words) rather than prefixes (the start of the words), since words that share the same suffix can be encoded together.

2. For every word, we traverse from its last character to the first character, corresponding to a path from the root to a leaf in the Trie. If the current character doesn't exist in the Trie at the current level, we create a new Trie node.

3. After all words are in the Trie, we need to find the encoded string's length. We do this by performing a depth-first search (DFS) on the Trie.

4. The DFS traversal keeps count of the length of each word that cannot be further combined into another word (a leaf node in the Trie). This is identified when a child node doesn't exist for the current path when traversing the Trie, indicating the end of an encoded word.

5. Whenever we reach a leaf node during DFS, we add the depth of the node (the length of the word) plus 1 to the result (the plus 1 accounts for the '#' at the end of every word).

6. The sum of these lengths for all the leaf nodes gives us the length of the shortest possible reference string.

In summary, by using a Trie to group suffixes, we avoid redundant encoding of words that are suffixes of other words. By performing a DFS, we calculate the sum of lengths of all unique word encodings (plus the '#' characters), achieving the desired result.

Learn more about Trie patterns.

Solution Approach

The solution to this problem uses a Trie data structure and a depth-first search (DFS) algorithm to find the minimum length of a reference string that can encode a given array of words. Here is a step-by-step implementation of the solution:

1. Trie Data Structure Setup: We start by defining a basic Trie node class that will hold an array of 26 elements for each letter in the lowercase English alphabet. Each element can point to another Trie node, representing the next character in a sequence of characters.

   1class [Trie](/problems/trie_intro):
   2    def __init__(self) -> None:
   3        self.children = [None] * 26

2. Reversing Words and Building the Trie: We initialize a root Trie node. For each word in the input list, we reverse the word and insert it into the Trie. The insertion is done by traversing the Trie nodes character by character from the reversed word starting at the root, creating new nodes when necessary. This loops from the end of the word to the beginning:

   1root = [Trie](/problems/trie_intro)()
   2for w in words:
   3    cur = root
   4    for i in range(len(w) - 1, -1, -1):
   5        idx = ord(w[i]) - ord('a')
   6        if cur.children[idx] == None:
   7            cur.children[idx] = Trie()
   8        cur = cur.children[idx]

3. Depth-First Search for Encoding Length: Once the Trie is built, we use the DFS algorithm to find all leaf nodes (nodes representing the last character of a unique word). The DFS function takes two arguments: the current node and the length of the word found till now (l), which starts at 1 to account for the terminating '#'. The DFS then proceeds as follows:

   • If a child node doesn't exist for any character, we know the current node is a leaf. When a leaf is encountered, the word length plus 1 for the terminating '#' is added to the total count (ans).
   • If a child node exists, recursively call DFS on the child, incrementing the length variable to track the growing word length.
   • The recursion terminated at leaf nodes, where it adds length to the total count.

   1def dfs(self, cur: [Trie](/problems/trie_intro), l: int) -> int:
   2    isLeaf, ans = True, 0
   3    for i in range(26):
   4        if cur.children[i] != None:
   5            isLeaf = False
   6            ans += self.dfs(cur.children[i], l + 1)
   7    if isLeaf:
   8        ans += l
   9    return ans

4. Calculating the Minimum Length: Finally, the DFS is initiated from the root of the Trie:

   1return self.dfs(root, 1)

The total count (ans) returned from the DFS is the length of the shortest reference string that can be generated from the given array of words. The DFS ensures that only the lengths of words that are not suffixes of any other word in the Trie are added, ensuring that the final answer is the minimum possible length.

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we are given the array of words ["time", "me", "bell"]. We need to find the shortest reference string that encodes these words according to the given problem description.

Following the solution approach, we proceed with these steps:

1. Reversing Words and Building the Trie

We start by initializing our Trie and reverse each word to focus on suffixes. This would give us the reversed words: ["emit", "em", "lleb"]. We then insert these words into the Trie by creating new nodes as necessary.

The Trie would look like this (represented conceptually, and not actual nodes):

1      root
2       |
3       e   <- 'time' and 'me'
4      /
5     m
6     | \
7     i  # <- end of 'me'
8    / 
9   t   <- end of 'time'
10  /
11 #      <- '#' represents the end of each word
12 |
13 l
14 |
15 l
16 |
17 e   <- end of 'bell'
18 |
19#      <- end of 'lleb'

2. Depth-First Search for Encoding Length

We define and use our dfs function to traverse the Trie and find all leaf nodes. In our Trie, the leaves are found at the end of "emit", "em", and "lleb".

As we traverse, we perform these steps:

• For "emit", we reach the end and find a leaf node. The length of the string plus 1 for '#' (5) is added.
• For "em", since "emit" has already been accounted for, it does not add any extra length.
• For "lleb", we reach another leaf node. The length of the string plus 1 for '#' (5) is added.

After calculating the lengths for all leaf nodes, we find the total length.

3. Calculating the Minimum Length

This traversal would give us:

• Length of "time#": 5 characters
• Length of "bell#": 5 characters

And since "me" is a suffix of "time", it does not add any additional length.

Therefore, the length of the shortest reference string is the sum of the lengths of individual words with '#' (which are not suffixes of any other word) is 5 (time#) + 5 (bell#) = 10.

Thus, our answer, in this case, would be 10, with the reference string being time#bell#.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of inserting a word into the Trie is O(L) where L is the length of the word. The for loop in minimumLengthEncoding method iterates over all the words and each character of each word, giving us a complexity of O(N*L) where N is the number of words and L is the average length of the words.

The dfs method has a time complexity of O(N*L) as well for the worst case, where each node is visited once. In the worst case, we can consider the depth of the Trie could be as long as the longest word, and each node could have 26 children if every character leads to a new word.

Therefore, the overall time complexity of the minimumLengthEncoding method is O(N*L).

Space Complexity

The space complexity is dictated by the storage needed for the Trie. Each node could potentially have 26 children, and the maximum depth of the Trie is L, the maximum length of a word. In the worst case, we'd have a completely full Trie where each node has 26 children, giving us a space complexity of O(26^L).

The recursive dfs method also contributes to the space complexity due to the call stack, which in the worst case could add up to O(L) depth for recursion.

Thus, the total worst-case space complexity is O(26^L + L), where O(26^L) is the dominant term.

Learn more about how to find time and space complexity quickly using problem constraints.