Sponsored
Sponsored
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.
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.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4
5class Solution:
6 def minimumLengthEncoding(self, words: List[str]) -> int:
7 # Use only unique words
8 words = set(words)
9 # Reverse sort words by length
10 words = sorted(words, key=lambda x: len(x), reverse=True)
11
12 root = TrieNode()
13 length = 0
14
15 for word in words:
16 current = root
17 isNew = False
18 # Insert word into the trie
19 for char in reversed(word):
20 if char not in current.children:
21 isNew = True
22 current.children[char] = TrieNode()
23 current = current.children[char]
24
25 # If it's a new path in trie, increase length
26 if isNew:
27 length += len(word) + 1
28
29 return lengthThis 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 '#'.
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.
Time Complexity: O(N * K^2), Space Complexity: O(N * K).
1class Solution:
2This 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.