Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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
}
linkedin
github
slack

Post Views: 10
Posted in MediumTagged #encoding, #trie

Post navigation

LeetCode: Fraction Addition and Subtraction
LeetCode: Serialize and Deserialize Binary Tree

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.