Short Encoding Of Words - Leetcode Solution

Problem Statement:

A valid encoding of an array of words is any reference string s and array of indices indices such that:

• words.length == indices.length
• The reference string s ends with the '#' character.
• For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character represents words[i].

Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

Example:

Input: words = ["time", "me", "bell"] Output: 10 Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 4, 6]. The encoded domain has minimum length because it only uses the minimum possible number of characters needed to encode the strings.

Solution:

We need to find the shortest possible reference string that can encode all the given words. Here we need to consider that each word should be encoded only once, i.e., if we have a word and it is already present as a substring in a previously encoded word, then we can ignore that word. This is because if we consider it, then it will increase the length of the encoding and not reduce it.

One approach to solve this problem is to first add all the words to a set as sets only allow unique elements. Then we can check each word's suffix if it is present in the set. If the suffix of the word is present, then we can ignore the word as it will be encoded in the previously encoded word itself. Otherwise, we add the word's suffix to the set.

Finally, we count the length of the strings present in the set and add the length of the set (which will be the number of '#' characters that will be present in the encoding) and return that as the answer.

Here is the Python code for the same:

class Solution: def minimumLengthEncoding(self, words: List[str]) -> int: word_set = set(words) for word in words: if word in word_set: for i in range(1, len(word)): word_set.discard(word[i:]) return sum(len(word) + 1 for word in word_set)

1