Básicamente mi duda trata sobre el bonus 5 de este problema del subreddit dailyprogrammer. Obviamente se que hay soluciones, pero quiero buscar una solución por mí mismo.
Así que os pregunto que estructura de datos usariais i/o el algoritmo para que la búsqueda sea rápida/eficiente y con el menor uso de memoria posible.
Siento no poderos copiar y pegar todo el problema, pero en el enlace del subreddit está bien explicado.
Saludos y buen domingo.
Una busqueda de elementos que no estan no puede ser mas eficiente que N. Y dependiendo del aalgoritmo, la memoria incluso n2.
En este caso o haria algo del tipo:
En 1 es donde esta el truco para la memoria. Si la codificacion es en string, por ejemplo, seria 2n ya que tienes que codificar las palabras y meterlas en la cadena, pero si encuentras otro tipo de dato (un hash?), que ocupe menos que la cadena se pueden rascar muchos bytes.
Para el smorse normal un map te vale
Para los bonus 1 y 2 un prefix tree.
Para el balanced tendria un map de letra = value, siendo el value la diff entre . y - recorrería la lista de palabras y les asignaría su valor a cada una según el mapa de letras. (no veo otra forma)
#4 Para el 5 arbol binario, vas a la prof 13 y breath first diria yo. Aunque si solo es para eso, puedes seguir esa lógica e ignorar todas las palabras que se queden en otra profundidad, y luego recorrer los nodos vacios (o que no existan) de la prof 13 e ya, que los puedes guardar en una lista enlazada por algo de performance.
Ya lo he solucionado, pero creo que no es lo más optimo. Al final lo que es un Map con todas las palabras cuya traduccion es mayor de 13 caracteres y luego iterar sobre todas las cadenas de 13 caracteres posibles y buscar si es substring. Me tarda 7 segundos en buscar.
#7 para que buscas? Si tienes todas las posibilidades solo tienes que borrar. Y si tienes un set/lista (no recuerdo exactamente) borrar es O(1)
#7 Con un árbol binario debería ser más rápido, pero creo que son los caminos con un nodo vacío los que cuentan, no las hojas, es decir, buscar nodos por los que nunca se pasó. (les puedes poner un flag true al pasar) y buscar los nodos que estén a false, y todos los caminos de ahi hacia abajo son un resultado.
Es prácticamente O(n logn) yo diría aunque no lo tengo claro del todo
#10 Lei mal el problema, no es que tengan que empezar o ser exactamente esa cadena, sino contener dicho substring... :\
Recuerdo hace muchos años cuando estaba en la carrera, este problema se solucionaba en teoría con un suffix tree, pero yo no fui capaz en su día de resolverlo.
#11 vale vale, he leido antes de tu edit y me estaba haciendo la paranoya, de todos modos gracias por currarte la respuesta 
Me miro lo del suffix tree.
#11 suffix tree es un overkill de la hostia teniendo en cuenta que el alfabeto es binario y la longitud fija y nada grande.
edit: #1 lee parrafo a parrafo para evitar spoilers
Con un array puedes. Una palabra en morse puede interpretarse como un numero en binario en la que los puntos son ceros y los guiones unos. O al reves, a gusto del consumidor.
Si lo miras asi, tienes 2 ** 13 palabras de longitud 13. Haz un array de 2 ** 13 = 8192 posiciones de booleanos y ve marcando trues segun veas las secuencias correspondientes.
Una vez termines el procesado iteras sobre el array y buscas los falses.
Overall complexity: O(n + 8192) = O(n), se puede hacer de una unica pasada si vas cambiando la mascara de bits acumulada bit a bit en lugar de substring a substring. Notemos que hacerlo por substrings no nos hace salirnos de coste lineal al ser 13 una constante.
Espacio adicional necesario (teoricamente podriamos resolverlo leyendo char a char): O(8192) = O(1)
Te dejo mi codigo en spoiler:
Y las palabras que me da de resultado: