LeetCode: Short Encoding of Words Posted on February 22, 2018July 26, 2020 by braindenny Short Encoding of Words Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #trie, #encoding 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. // 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 } Post Views: 10