SHARE
TWEET

Untitled

a guest Sep 18th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "unicode"
  6. )
  7.  
  8. type TrieNode struct {
  9.     isEndOfWord   bool
  10.     children [26]*TrieNode
  11. }
  12.  
  13. type Trie struct {
  14.     root TrieNode
  15. }
  16.  
  17. func (t *Trie) Add(s string) {
  18.     node := &t.root
  19.     for _, r := range s {
  20.         if unicode.IsLower(r) {
  21.             i := r - 'a'
  22.             if node.children[i] == nil {
  23.                 node.children[i] = &TrieNode{}
  24.             }
  25.             node = node.children[i]
  26.         } else {
  27.             panic("only lowercase letters are allowed")
  28.         }
  29.     }
  30.     node.isEndOfWord = true
  31. }
  32.  
  33. func (t *Trie) Has(s string) bool {
  34.     node := &t.root
  35.     for _, r := range s {
  36.         if unicode.IsLower(r) {
  37.             i := r - 'a'
  38.             if node.children[i] == nil {
  39.                 return false
  40.             }
  41.             node = node.children[i]
  42.         } else {
  43.             panic("only lowercase letters are allowed")
  44.         }
  45.     }
  46.     return node.isEndOfWord
  47. }
  48.  
  49. func (t *Trie) All() []string {
  50.     var traverse func(*TrieNode, string) []string
  51.     traverse = func(node *TrieNode, s string) []string {
  52.         var result []string
  53.         if node.isEndOfWord {
  54.             result = append(result, s)
  55.         }
  56.         for i, c := range node.children {
  57.             if c != nil {
  58.                 result = append(result, traverse(c, string(append([]rune(s), rune('a'+i))))...)
  59.             }
  60.         }
  61.         return result
  62.     }
  63.     return traverse(&t.root, "")
  64. }
  65.  
  66. func main() {
  67.     t := &Trie{}
  68.     t.Add("hello")
  69.     t.Add("world")
  70.     t.Add("hell")
  71.     fmt.Println(t.All())
  72.     fmt.Println(t.Has("hell"))
  73. }
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