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 ofs
starting fromindices[i]
and up to (but not including) the next'#'
character is equal towords[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 {
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.