## 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:10Explanation: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:2Explanation: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.

## Rust Solution

```
struct Solution;
use std::collections::HashMap;
#[derive(PartialEq, Eq, Default)]
struct Trie {
children: HashMap<char, Trie>,
end: bool,
}
impl Trie {
fn new() -> Self {
Self::default()
}
fn insert<I>(&mut self, iter: I)
where
I: Iterator<Item = char>,
{
let mut link = self;
for c in iter {
link = link.children.entry(c).or_default();
}
link.end = true;
}
fn dfs(&self, length: usize, sum: &mut usize) {
let mut is_leaf = true;
for link in self.children.values() {
is_leaf = false;
link.dfs(length + 1, sum);
}
if is_leaf {
*sum += length + 1;
}
}
}
impl Solution {
fn minimum_length_encoding(words: Vec<String>) -> i32 {
let mut trie = Trie::new();
for word in words {
trie.insert(word.chars().rev());
}
let mut res = 0;
trie.dfs(0, &mut res);
res as i32
}
}
#[test]
fn test() {
let words = vec_string!["time", "me", "bell"];
let res = 10;
assert_eq!(Solution::minimum_length_encoding(words), res);
}
```

Having problems with this solution? Click here to submit an issue on github.