golang 实现字符串匹配算法Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

package main

import "fmt"

type TrieNode struct {
    Date string
    Children map[string]*TrieNode
    IsEndingChar bool
}

type GoTrie struct {
    Root *TrieNode
}

func (this *GoTrie) Insert(text string) {

    p := this.Root

    for i:=0; i < len(text); i++ {
        index := string(text[i])
        data := index
        if p.Children == nil {
            p.Children = make(map[string]*TrieNode)
        }
        if _, ok := p.Children[index]; !ok {
            newNode := &TrieNode{
                Date:data,
            }
            p.Children[index] = newNode
        }

        p = p.Children[index]
    }

    p.IsEndingChar = true
}

func (this *GoTrie) Find(pattern string) bool {
    p := this.Root

    for i:=0; i<len(pattern); i++ {
        index := string(pattern[i])

        if _, ok := p.Children[index]; !ok {
            return false
        }

        p = p.Children[index]
    }

    if p.IsEndingChar == false {
        return false
    }
    return true
}

func main(){
    strs := [...]string{"Laravel", "Framework", "PHP"}
    trie := &GoTrie{}
    trie.Root = &TrieNode{}

    for _, str := range strs {
        trie.Insert(str)
    }

    fmt.Println(trie.Root.Children["F"].Children)

    fmt.Println(trie.Find("PHP"))
    fmt.Println(trie.Find("PHPA"))
}