95 lines
1.4 KiB
Go
95 lines
1.4 KiB
Go
|
package main
|
||
|
|
|
||
|
|
import (
|
||
|
|
"bufio"
|
||
|
|
"fmt"
|
||
|
|
"io"
|
||
|
|
"os"
|
||
|
|
"strconv"
|
||
|
|
"strings"
|
||
|
|
)
|
||
|
|
|
||
|
|
/*
|
||
|
|
* Complete the 'noPrefix' function below.
|
||
|
|
*
|
||
|
|
* The function accepts STRING_ARRAY words as parameter.
|
||
|
|
*/
|
||
|
|
|
||
|
|
type trie struct {
|
||
|
|
wordEnd bool
|
||
|
|
child [10]*trie
|
||
|
|
}
|
||
|
|
|
||
|
|
func (m *trie) add(word string) {
|
||
|
|
curr := m
|
||
|
|
for _, r := range word {
|
||
|
|
index := r - 'a'
|
||
|
|
if curr.child[index] == nil {
|
||
|
|
curr.child[index] = &trie{}
|
||
|
|
}
|
||
|
|
curr = curr.child[index]
|
||
|
|
}
|
||
|
|
curr.wordEnd = true
|
||
|
|
}
|
||
|
|
|
||
|
|
func (m *trie) find(word string) bool {
|
||
|
|
curr := m
|
||
|
|
for _, r := range word {
|
||
|
|
index := r - 'a'
|
||
|
|
if curr.child[index] != nil {
|
||
|
|
curr = curr.child[index]
|
||
|
|
|
||
|
|
if curr.wordEnd {
|
||
|
|
return true
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
return false
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return true
|
||
|
|
}
|
||
|
|
|
||
|
|
func noPrefix(words []string) {
|
||
|
|
tree := &trie{}
|
||
|
|
|
||
|
|
for _, word := range words {
|
||
|
|
if tree.find(word) {
|
||
|
|
fmt.Print("BAD SET\n", word)
|
||
|
|
return
|
||
|
|
}
|
||
|
|
tree.add(word)
|
||
|
|
}
|
||
|
|
fmt.Println("GOOD SET")
|
||
|
|
}
|
||
|
|
func main() {
|
||
|
|
reader := bufio.NewReaderSize(os.Stdin, 16*1024*1024)
|
||
|
|
|
||
|
|
nTemp, err := strconv.ParseInt(strings.TrimSpace(readLine(reader)), 10, 64)
|
||
|
|
checkError(err)
|
||
|
|
n := int32(nTemp)
|
||
|
|
|
||
|
|
var words []string
|
||
|
|
|
||
|
|
for i := 0; i < int(n); i++ {
|
||
|
|
wordsItem := readLine(reader)
|
||
|
|
words = append(words, wordsItem)
|
||
|
|
}
|
||
|
|
|
||
|
|
noPrefix(words)
|
||
|
|
}
|
||
|
|
|
||
|
|
func readLine(reader *bufio.Reader) string {
|
||
|
|
str, _, err := reader.ReadLine()
|
||
|
|
if err == io.EOF {
|
||
|
|
return ""
|
||
|
|
}
|
||
|
|
|
||
|
|
return strings.TrimRight(string(str), "\r\n")
|
||
|
|
}
|
||
|
|
|
||
|
|
func checkError(err error) {
|
||
|
|
if err != nil {
|
||
|
|
panic(err)
|
||
|
|
}
|
||
|
|
}
|