Introdução
Uma árvore de raiz , também conhecida como árvore compactada trie ou prefixo compactado, é uma estrutura de dados semelhante a uma árvore para armazenar um conjunto de cadeias. As bordas da árvore são rotuladas por cadeias não vazias e cada nó é terminal ou não terminal. As strings que a árvore contém são exatamente os rótulos de todos os caminhos, da raiz ao nó do terminal. A árvore deve estar na forma normal definida pelas seguintes condições:
- Todos os nós não-raiz não-terminais têm pelo menos dois filhos.
- Para cada nó, todas as arestas de saída têm primeiros caracteres diferentes.
Por exemplo, aqui está a árvore de raiz que contém o conjunto ["test", "testing", "tested", "team", "teams", "technical", "sick", "silly"]
, (N)
representando um nó não terminal e (T)
um nó terminal:
-(N)-te-(N)-st-(T)-ing-(T)
| | |
| | +-ed-(T)
| |
| +-am-(T)-s-(T)
| |
| +-chnical-(T)
|
+-si-(N)-ck-(T)
|
+-lly-(T)
Nesse desafio, sua tarefa é calcular a altura da árvore, considerando as seqüências de caracteres como entrada.
Entrada
Sua entrada é uma lista não vazia de cadeias de letras ASCII em minúsculas. Não conterá duplicatas, mas pode estar em qualquer ordem. Pode conter a cadeia vazia. Você pode receber a entrada em qualquer formato razoável.
Resultado
Sua saída deve ser o comprimento do caminho raiz-a-folha mais longo na árvore de raiz correspondente, medida no número de nós que ela contém.
No exemplo acima, a saída correta é 4, correspondendo aos caminhos
(N)-te-(N)-st-(T)-ing-(T)
(N)-te-(N)-st-(T)-ed-(T)
(N)-te-(N)-am-(T)-s-(T)
que contêm 4 nós.
Outros exemplos
Aqui estão mais alguns exemplos de árvores de raiz:
[""]
-(T)
["","fuller"]
-(T)-fuller-(T)
["","full","fuller"]
-(T)-full-(T)-er-(T)
["full","fuller"]
-(N)-full-(T)-er-(T)
["full","filler"]
-(N)-f-(N)-ull-(T)
|
+-iller-(T)
Regras e pontuação
Você pode escrever um programa completo ou uma função. Isso é código de golfe, portanto, a menor contagem de bytes vence.
Você pode usar qualquer built-in ou bibliotecas que desejar, mas lembre-se de incluir todos os import
s etc. em sua contagem de bytes. Bibliotecas de terceiros - aquelas que não estão incluídas na instalação padrão do seu idioma - são permitidas, mas devem ser listadas no cabeçalho separadamente, por exemplo, Python + pytrie0.2, 60 bytes .
Casos de teste
[""] -> 1
["fuller"] -> 2
["","fuller"] -> 2
["","full","fuller"] -> 3
["full","fuller"] -> 3
["full","filler"] -> 3
["full","filler","filter"] -> 4
["full","filler","fi","filter"] -> 5
["test","testing","tested","team","teams","technical","sick","silly"] -> 4
["a","aaaa","aabbaa","aabbaab","abaaa","aab","aabbb","aabba"] -> 8
["dbdbaca","ab","a","caaabaaa","adbbabdb","dbdbdbaca","dbbadbacaba","db"] -> 4
["db","dbbdbb","dbaa","cabcacaa","","acaabcacab","b","abaaaca","bacaaaaa"] -> 3
["aabaabdbb","bacaabadbbdb","abb","aabaa","ab","bcadbb","adbbcaaadbbb","caaa","bbdbcacadbab","dbbdbdb"] -> 4
["bbcaaabbbabbcadbbacadbbdbdb","b","bbbbaaaaaababa","ca","bb","bdbbacadbbdbbdbbababaacaca","abbaabbabcabaaa","bbbacacacabcacacabaaabb","bbcaaaab","bbbbcaacaadbcaaa","babbabcadbdbacacabbcacab","abcabbbaacadbcadb","bbcabbcadbcacaacaadbadbcaadb","dbbbdbbdbacaabbacabcadbdbacaca","bbaabdbdb","cabcadbbbadbadbbaadbcaca","adbadbadbdbcacadbdbbcaadbcaca","abaabbcab","aaabcaabcaab","bacacabcacaacadbadbb"] -> 6
Respostas:
JavaScript (Firefox 30-57), 137 bytes
Deve haver algo errado com o meu algoritmo, pois eu pareço ter um caso especial com um parâmetro de string vazio.
fonte
.
no final da primeira linha).Retina ,
6955 bytesO avanço de linha à direita é significativo.
Entrada é uma lista separada por avanço de linha.
O desempenho pode ser aumentado significativamente inserindo um
\A
antes do último\D
na primeira linha.Explicação
Um nó é inserido em uma palavra em três lugares:
Na Retina, tende a ser mais curto para produzir
N+1
quando você conta asN
coisas, então estamos ignorando a que está no final. No entanto, para o caso da entrada vazia, também teremos que ignorar o início, porque começo e fim são os mesmos.Para fazer a contagem real, inserimos
:
em todos os lugares onde há um nó. Então, simplesmente encontramos o número máximo de:
em uma palavra e retornamos mais 1. Aqui está como o código faz isso:Isso detecta todos os nós. Corresponde a um personagem. Em seguida, entra em um lookbehind que captura esse caractere em grupo
2
e o prefixo antes dele em grupo1
. Em seguida, ele vai todo o caminho para o início da cadeia para iniciar um lookahead, que verifica se ele pode encontrar o lugar prefixo onde ele está não seguido pelo caractere capturado. Se encontrarmos essa correspondência, inserimos um:
na frente do caractere. Também combinamos o primeiro caractere da palavra atual para inserir a:
no início das palavras não vazias.Isso remove todas as letras e deixa apenas o
:
.Isso classifica as linhas, trazendo a profundidade máxima até o fim.
Isso descarta tudo, exceto a última linha.
E a linha vazia no final conta o número de correspondências vazias nessa linha, que é uma a mais que o número de dois pontos nela.
Experimente online! (A primeira linha ativa um conjunto de testes separado por avanço de linha, onde cada caso de teste usa separação por vírgula.)
fonte