# Leetcode: Short Encoding of Words

Short Encoding of Words

Similar Problems:

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is [“time”, “me”, “bell”], we can write it as S = “time#bell#” and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

```Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].
```

Note:

• 1 <= words.length <= 2000.
• 1 <= words[i].length <= 7.
• Each word has only lowercase letters.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```// Blog link: https://code.dennyzhang.com/short-encoding-of-words
// Basic Ideas: Trie (One pass, instead of two)
//     Reverse the words, build trie tree
//     Get the length from the items in the tree
//
//     Note: the expression is not unique
//      Both: "time#bell#" and "bell#time#" are fine
//  Assumptions: no duplicate words
//
// Complexity: Time O(n), Space O(n)
//    n = total count of characters in all words

type TrieNode struct {
is_leaf bool
children map[byte]*TrieNode
}

func minimumLengthEncoding(words []string) int {
// build TrieTree
res := 0
leaf_count := 0

root := TrieNode{children: make(map[byte]*TrieNode)}
for _, word := range words {
p := &root
for i:=len(word)-1; i>=0; i-- {
ch := word[i]
q, status := p.children[ch]
if status == false {
q = &TrieNode{children: make(map[byte]*TrieNode)}
p.children[ch] = q
}
p = q
res += 1
if p.is_leaf == true {
// revert
p.is_leaf = false
leaf_count -= 1
res -= (len(word) - i)
}
}
p.is_leaf = true
leaf_count += 1
if len(p.children) != 0 {
// revert
p.is_leaf = false
leaf_count -= 1
res -= len(word)
}
}
return res + leaf_count
}
```

Share It, If You Like It.