lc.go

package main

import "sort"

type byLength []string

func (s byLength) Len() int {
	return len(s)
}

func (s byLength) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s byLength) Less(i, j int) bool {
	return len(s[i]) < len(s[j])
}

func longestChain(words []string) int32 {
	sort.Sort(byLength(words))

	dict := map[string]int32{}

	var longest int32 = 1
	shortest := len(words[0])
	for _, word := range words {
		if len(word) == shortest {
			dict[word] = 1
			continue
		}
		var chain int32 = 1
		var tl int32 = 0
		for i := 0; i < len(word); i++ {
			s := word[:i] + word[i+1:]

			if found, ok := dict[s]; ok {
				if found > tl {
					tl = found
				}
			}
		}
		chain += tl
		dict[word] = chain

		if chain > longest {
			longest = chain
		}
	}

	return longest
}

func main() {
	result := longestChain([]string{
		"a",
		"b",
		"e",
		"de",
		"ba",
		"bca",
		"bda",
		"bdca",
		"bdeca",
		"bdfac",
	})
	println(result)
}