Calcular la altura de un árbol radix

Introducción

Un árbol radix , también conocido como trie comprimido o árbol de prefijos comprimido, es una estructura de datos similar a un árbol para almacenar un conjunto de cadenas. Los bordes del árbol están etiquetados por cadenas no vacías, y cada nodo es terminal o no terminal. Las cadenas que contiene el árbol son exactamente las etiquetas de todas las rutas desde la raíz hasta un nodo terminal. El árbol debe estar en la forma normal definida por las siguientes condiciones:

• Todos los nodos no raíz no terminales tienen al menos dos hijos.
• Para cada nodo, todos los bordes salientes tienen primeros caracteres diferentes.

Por ejemplo, aquí está el árbol de la raíz que contiene el conjunto ["test", "testing", "tested", "team", "teams", "technical", "sick", "silly"], con la (N)representación de un nodo no terminal y (T)un nodo terminal:

-(N)-te-(N)-st-(T)-ing-(T)
  |      |      | 
  |      |      +-ed-(T)
  |      |
  |      +-am-(T)-s-(T)
  |      |
  |      +-chnical-(T)
  |
  +-si-(N)-ck-(T)
        |
        +-lly-(T)

En este desafío, su tarea es calcular la altura del árbol, dadas las cadenas como entrada.

Entrada

Su entrada es una lista no vacía de cadenas de letras minúsculas ASCII. No contendrá duplicados, pero puede estar en cualquier orden. Puede contener la cadena vacía. Puede tomar la entrada en cualquier formato razonable.

Salida

Su salida será la longitud de la ruta de raíz a hoja más larga en el árbol de raíz correspondiente, medida en el número de nodos que contiene.

En el ejemplo anterior, la salida correcta es 4, correspondiente a las rutas

(N)-te-(N)-st-(T)-ing-(T)
(N)-te-(N)-st-(T)-ed-(T)
(N)-te-(N)-am-(T)-s-(T)

que contienen 4 nodos.

Ejemplos adicionales

Aquí hay un par de ejemplos más de árboles radix:

[""]
-(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)

Reglas y puntaje

Puede escribir un programa completo o una función. Este es el código de golf, por lo que gana el conteo de bytes más bajo.

Puede utilizar cualquier biblioteca o biblioteca incorporada que desee, pero recuerde incluir todos importlos correos electrónicos, etc., en su recuento de bytes. Las bibliotecas de terceros, aquellas que no están incluidas en la instalación estándar de su idioma, están permitidas, pero deben aparecer en el encabezado por separado, por ejemplo, Python + pytrie0.2, 60 bytes .

Casos de prueba

[""] -> 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

JavaScript (Firefox 30-57), 137 bytes

f=(a,b=["",...a],s=new Set(b.map(w=>w[0])))=>b.length>1?(s.size>1)+Math.max(...(for(c of s)f(a,[for(w of b)if(w&&w[0]==c)w.slice(1)]))):1

Debe haber algo mal con mi algoritmo, ya que parece que tengo que hacer un caso especial de un parámetro de cadena vacío.

Retina , 69 55 bytes

El avance de línea final es significativo.

m`.(?<=(?=\D*^\1(?!\2))\D*^(.*)(.))|^.
:$&
T`w
O`
A-2`

La entrada es una lista separada por salto de línea.

El rendimiento se puede aumentar significativamente insertando un \Aantes del último \Den la primera línea.

Explicación

Un nodo se inserta en una palabra en tres lugares:

• El principio.
• Después de cualquier prefijo más largo compartido con otra palabra. Es decir, un prefijo compartido después del cual las dos palabras difieren.
• El fin.

En Retina, tiende a ser más corto de producir N+1cuando has contado Ncosas, por lo que estamos ignorando el que está al final. Sin embargo, para el caso de la entrada vacía, también tendremos que ignorar el inicio, porque principio y fin son lo mismo.

Para hacer el conteo real, insertamos :en cada lugar donde hay un nodo. Luego, simplemente encontramos el número máximo de :en una palabra y devolvemos ese más 1. Así es como lo hace el código:

m`.(?<=(?=\D*^\1(?!\2))\D*^(.*)(.))|^.
:$&

Esto detecta todos los nodos. Coincide con un personaje. Luego ingresa una mirada hacia atrás que captura a ese personaje en grupo 2y el prefijo anterior a él en grupo 1. Entonces va todo el camino hasta el comienzo de la cadena para iniciar una búsqueda hacia delante, lo que comprueba que se puede encontrar en algún lugar del prefijo donde está no sigue el espacio capturado. Si encontramos esta coincidencia, insertamos un :en frente del personaje. También hacemos coincidir el primer carácter de la palabra actual para insertar un :al principio de las palabras no vacías.

T`w

Esto elimina todas las letras y deja solo el :.

O`

Esto ordena las líneas, llevando la profundidad máxima al final.

A-2`

Esto descarta todos menos la última línea.

Y la línea vacía al final cuenta el número de coincidencias vacías en esa línea, que es uno más que el número de dos puntos en ella.

Pruébalo en línea! (La primera línea habilita un conjunto de pruebas separadas por salto de línea, donde cada caso de prueba utiliza la separación por comas).