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.

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 {
}
}

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.