daily pastebin goal
45%
SHARE
TWEET

Untitled

a guest May 17th, 2018 119 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. PROBLEM
  3.  
  4. Given a list of words, we may encode it by writing a reference string S and a list of indexes A.
  5.  
  6. For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].
  7.  
  8. Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.
  9.  
  10. What is the length of the shortest reference string S possible that encodes the given words?
  11.  
  12. Example:
  13.  
  14. Input: words = ["time", "me", "bell"]
  15. Output: 10
  16. Explanation: S = "time#bell#" and indexes = [0, 2, 5].
  17. Note:
  18.  
  19. 1 <= words.length <= 2000.
  20. 1 <= words[i].length <= 7.
  21. Each word has only lowercase letters.
  22.  
  23. */
  24.  
  25.  
  26. // SOLUTION
  27.  
  28. import "sort"
  29.  
  30. // trie datastructure
  31. type TrieNode struct {
  32.     Val string
  33.     Children []*TrieNode
  34. }
  35.  
  36.  
  37. type byLength []string
  38.  
  39. func (s byLength) Len() int {
  40.     return len(s)
  41. }
  42.  
  43. func (s byLength) Swap(i, j int) {
  44.     s[i], s[j] = s[j], s[i]
  45. }
  46.  
  47. // rig it -- we want the longest words FIRST. so less means whichever is longer length
  48. func (s byLength) Less(i, j int) bool {
  49.     if len(s[i]) > len(s[j]) {
  50.         return true
  51.     }
  52.     return false
  53. }
  54.  
  55.  
  56. func minimumLengthEncoding(words []string) int {
  57.    
  58.     // have to sort words by length
  59.     sort.Sort(byLength(words))
  60.     fmt.Printf("SORTED: %#v\n", words)
  61.    
  62.     trie := &TrieNode{Val: "", Children: []*TrieNode{}}
  63.     total := 0
  64.     kept := 0
  65.     // construct the suffix tree by working backwards through each string in "words."
  66.     // one character per list node.
  67.     for _, w := range words {
  68.         leaf := add(trie, w)
  69.         if leaf {  
  70.             kept += 1
  71.             total += len(w)
  72.             fmt.Printf("%s is a new leaf, adding 1 to kept (now %d), adding %d to total (now %d)\n", w, kept, len(w), total)
  73.         } else {
  74.             fmt.Printf("%s is embedded already\n", w)
  75.         }
  76.     }
  77.     return total + kept
  78. }
  79.  
  80.  
  81. /*
  82. when adding, we keep track of if my first letter is a leaf.
  83. if NOT a leaf, return false (I'm folded into the encoding)
  84. if I AM a leaf, return true
  85. */
  86. //  "" -> e -> m -> i -> t
  87. //     -> l -> l -> e -> b
  88. func add(trie *TrieNode, w string) bool {
  89.     //fmt.Printf("Adding word to trie: %s\n", w)
  90.     if len(w) == 0 {
  91.         return false
  92.     }
  93.     newPath := false
  94.     for i := len(w)-1; i >= 0; i-- {
  95.         found := inChildren(trie, string(w[i]))
  96.         if found == -1 {
  97.             newPath = true
  98.             trie.Children = append(trie.Children, &TrieNode{Val: string(w[i]), Children: []*TrieNode{}})
  99.             trie = trie.Children[len(trie.Children)-1]
  100.         } else {
  101.             trie = trie.Children[found]
  102.         }  
  103.     }
  104.     // check if leaf that forged a new path (not a duplicate word)
  105.     if len(trie.Children) == 0 && newPath {
  106.         return true
  107.     }
  108.     return false
  109. }
  110.  
  111. func inChildren(trie *TrieNode, char string) int {
  112.     if trie == nil {
  113.         return -1
  114.     }
  115.     for i, child := range trie.Children {
  116.         if child.Val == char {
  117.             return i
  118.         }
  119.     }
  120.     return -1
  121. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top