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 constructor() {
3 this.children = {};
4 }
5}
6
7var minimumLengthEncoding = function(words) {
8 let root = new TrieNode();
9 let leaves = new Set();
10
11 for (let word of words) {
12 let node = root;
13 for (let i = word.length - 1; i >= 0; i--) {
14 let char = word[i];
15 if (!node.children[char]) {
16 node.children[char] = new TrieNode();
17 }
18 node = node.children[char];
19 }
20 leaves.add(node);
21 }
22
23 let length = 0;
24 for (let leaf of leaves) {
25 if (Object.keys(leaf.children).length === 0) {
26 length += word.length + 1;
27 }
28 }
29
30 return length;
31};JavaScript employs similar Trie construction and suffix tracking. By focusing on the leaf nodes with no children, the function calculates the encoded string length by summing distinct word lengths with '#' separators.
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).
1using System;
2using System.Collections.Generic;
class Solution {
public int MinimumLengthEncoding(string[] words) {
HashSet<string> uniqueWords = new HashSet<string>(words);
List<string> sortedWords = new List<string>(uniqueWords);
sortedWords.Sort((a, b) => string.Compare(b, a, StringComparison.Ordinal));
foreach (string word in sortedWords) {
for (int i = 1; i < word.Length; i++) {
uniqueWords.Remove(word.Substring(i));
}
}
int length = 0;
foreach (string word in uniqueWords) {
length += word.Length + 1;
}
return length;
}
}The solution in C# benefits from the sorted word manipulation and distinct word tracking methods, efficiently computing valid encodings with required components and separators.