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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <unordered_set>
5using namespace std;
6
7struct TrieNode {
8 unordered_map<char, TrieNode*> children;
9};
10
11class Solution {
12public:
13 int minimumLengthEncoding(vector<string>& words) {
14 TrieNode* root = new TrieNode();
15 unordered_set<TrieNode*> leaves;
16
17 for (auto& word : words) {
18 TrieNode* node = root;
19 for (int i = word.size() - 1; i >= 0; --i) {
20 if (!node->children.count(word[i])) {
21 node->children[word[i]] = new TrieNode();
22 }
23 node = node->children[word[i]];
24 }
25 leaves.insert(node);
26 }
27
28 int length = 0;
29 for (auto& leaf : leaves) {
30 if (leaf->children.empty()) {
31 length += word.length() + 1;
32 }
33 }
34
35 return length;
36 }
37};This C++ solution adopts a similar approach as Python, constructing a Trie in which words (or suffixes of words) are inserted in reverse, and a node pointer set collects potential ends of words. Only nodes with an empty set of child nodes actively contribute to the total encoding length.
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: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.