题解 | #字符串排序#

照理说简单题不应该考这种内容, 但是我做算法历来的习惯就是不调语言的 api, 允许的话那 Python 做算法也太轻松了

第一反应是字典树, 实现了一下, 就是第一次 submit 没想到还有重复值

package main

import (
	"fmt"
)

type TrieNode struct {
	Char     string
	Children []*TrieNode
	Endpoint bool
	Count    int
}

func NewTrieNode(c string) *TrieNode {
	children := make([]*TrieNode, 52)
	return &TrieNode{Char: c, Children: children, Endpoint: false}
}

type Trie struct {
	Root *TrieNode
}

func (t *Trie) AddNode(word string) {
	node := t.Root
	for i := 0; i < len(word); i++ {
		c := word[i]
		idx := c - 'A'
		if idx > 25 {
			idx -= 6
		}
		if node.Children[idx] == nil {
			node.Children[idx] = NewTrieNode(string(c))
		}
		if i == len(word)-1 {
			node.Children[idx].Endpoint = true
			node.Children[idx].Count++
		}
		node = node.Children[idx]
	}
}

func traverseNode(node *TrieNode, path string) {
	if node.Endpoint {
		for i := 0; i < node.Count; i++ {
			fmt.Println(path + node.Char)
		}
	}

	for _, n := range node.Children {
		if n != nil {
			traverseNode(n, path+node.Char)
		}
	}
}

func (t *Trie) Traverse() {
	traverseNode(t.Root, "")
}

func NewTrie() *Trie {
	return &Trie{Root: NewTrieNode("")}
}

func main() {
	n := 0
	fmt.Scan(&n)
	t := NewTrie()

	s := ""
	for {
		m, _ := fmt.Scan(&s)
		if m == 0 {
			break
		} else {
			t.AddNode(s)
		}
	}

	t.Traverse()
}