3.go

// https://leetcode.com/problems/longest-common-prefix/

package main

type TrieNode struct {
	children    map[rune]*TrieNode
	isEndOfWord bool
}

func insert(root *TrieNode, key string) {
	currentNode := root
	for _, char := range key {
		if node, ok := currentNode.children[char]; ok {
			currentNode = node
		} else {
			newNode := TrieNode{children: make(map[rune]*TrieNode), isEndOfWord: false}
			currentNode.children[char] = &newNode
			currentNode = &newNode
		}
	}
	currentNode.isEndOfWord = true
}

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	if len(strs) == 1 {
		return strs[0]
	}

	trieHead := &TrieNode{children: make(map[rune]*TrieNode)}

	for _, str := range strs {
		if str == "" {
			return ""
		}
		insert(trieHead, str)
	}

	if len(trieHead.children) != 1 {
		return ""
	}

	return getLongestCommonPrefix(trieHead)
}

func getLongestCommonPrefix(head *TrieNode) string {
	result := ""
	for key, node := range head.children {
		result += string(key)

		if len(node.children) != 1 || node.isEndOfWord {
			break
		}

		return result + getLongestCommonPrefix(node)
	}
	return result
}