A valid encoding of an array of words is any reference string s and array of indices indices such that:
words.length == indices.lengths ends with the '#' character.indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i].Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.
Example 1:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"
Example 2:
Input: words = ["t"] Output: 2 Explanation: A valid encoding would be s = "t#" and indices = [0].
Constraints:
1 <= words.length <= 20001 <= words[i].length <= 7words[i] consists of only lowercase letters.This approach involves building a trie that can be used to efficiently check if one word is a suffix of another. By storing only the unique paths in the trie, the encoding length can be minimized by pointing out the redundancies where one word is a suffix of another.
This solution uses a Trie (prefix tree) to store words in reversed order. It checks whether inserting a word introduces new paths in the Trie, indicating that it isn't a suffix of any word already added. For every new path, the length increases by the length of the word plus one for the '#'.
C++
Java
C#
JavaScript
Time Complexity: O(N * K) where N is the number of words and K is the average length of a word.
Space Complexity: O(N * K) due to the storage in the Trie.
By reverse sorting the words and checking suffix existence, it's possible to efficiently determine the redundant entries. This alternative approach utilizes set operations to ascertain unique encodings, optimizing storage by including only necessary components.
This method sorts the words by reversed string, facilitating checks for suffixes as subsequent entries. By discarding suffixes and iterating over the unique words, it computes the total length effectively.
C++
Java
C#
JavaScript
Time Complexity: O(N * K^2), Space Complexity: O(N * K).
| Approach | Complexity |
|---|---|
| Using Suffix Trie | Time Complexity: O(N * K) where N is the number of words and K is the average length of a word. |
| Reverse Sorting and Set | Time Complexity: O(N * K^2), Space Complexity: O(N * K). |
Short Encoding of Words | Live Coding with Explanation | Leetcode - 820 • Algorithms Made Easy • 4,031 views views
Watch 9 more video solutions →Practice Short Encoding of Words with our built-in code editor and test cases.
Practice on FleetCode