## Algorithm

Problem Name: 820. Short Encoding of Words

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 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 <= 2000`
• `1 <= words[i].length <= 7`
• `words[i]` consists of only lowercase letters.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
private:
struct TrieNode{
int length;
bool isWord;
vector < TrieNode*>next;
TrieNode(int x): length(x), isWord(false), next(vector<TrieNode*>(26)){}
};
TrieNode* root;

public:
int minimumLengthEncoding(vector < string>& words) {
root = new TrieNode(0);
int count = 0;
for(auto& s: words){
reverse(s.begin(), s.end());
buildTrie(s, count);
}
return count;
}

void buildTrie(string& s, int& count){
auto p = root;
bool newWord = false;
for(int i = 0; i  <  s.size(); i++){
char c = s[i];
if(!p->next[c - 'a']){
if(!newWord){
count++;
if(p->isWord){
count--;
count -= p->length;
p->isWord = false;
}
newWord = true;
}
p->next[c - 'a'] = new TrieNode(i + 1);
}
p = p->next[c - 'a'];
}
if(newWord){
count += p->length;
p->isWord = true;
}
}
};
``````
Copy The Code &

Input

cmd
words = ["time", "me", "bell"]

Output

cmd
10

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int minimumLengthEncoding(String[] words) {
TrieNode root = new TrieNode();
Map < TrieNode, Integer> nodes = new HashMap<>();
for (int i = 0; i  <  words.length; i++) {
TrieNode curr = root;
for (int j = words[i].length() - 1; j >= 0; j--) {
if (curr.children[words[i].charAt(j) - 'a'] == null) {
curr.children[words[i].charAt(j) - 'a'] = new TrieNode();
curr.count++;
}
curr = curr.children[words[i].charAt(j) - 'a'];
}
nodes.put(curr, i);
}
int result = 0;
for (TrieNode node : nodes.keySet()) {
if (node.count == 0) {
result += words[nodes.get(node)].length() + 1;
}
}
return result;
}

private class TrieNode {
TrieNode[] children;
int count;

public TrieNode() {
this.children = new TrieNode[26];
this.count = 0;
}
}
}
``````
Copy The Code &

Input

cmd
words = ["time", "me", "bell"]

Output

cmd
10

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minimumLengthEncoding(self, words):
"""
:type words: List[str]
:rtype: int
"""
s = set(words)
for word in words:
for i in range(1, len(word)): s.discard(word[i:])
return sum(len(w) + 1 for w in s)
``````
Copy The Code &

Input

cmd
words = ["t"]

Output

cmd
2