• API
• FAQ
• Tools
• Archive
daily pastebin goal
51%
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.     }
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.

Top