LeetCode/go/string-matching-in-an-array.go

package main

type TrieNode struct {
	frequency int
	children  map[rune]*TrieNode
}

func NewNode() *TrieNode {
	return &TrieNode{
		frequency: 0,
		children:  make(map[rune]*TrieNode),
	}
}

func (node *TrieNode) Insert(word string) {
	n := node
	for _, c := range word {
		_, ok := n.children[c]
		if !ok {
			n.children[c] = NewNode()
		}

		n = n.children[c]
		n.frequency++
	}
}

func (node *TrieNode) IsSubstring(word string) bool {
	n := node
	for _, c := range word {
		n = n.children[c]
	}

	return n.frequency > 1
}

func stringMatching(words []string) []string {
	matching := make([]string, 0)

	root := NewNode()
	for _, word := range words {
		for start := 0; start < len(word); start++ {
			root.Insert(word[start:])
		}
	}

	for _, word := range words {
		if root.IsSubstring(word) {
			matching = append(matching, word)
		}
	}

	return matching
}