Lenguaje de los antiguos

[GabrielEValenzuela]

Descripción

En el universo del juego, el jugador encuentra un códice antiguo que contiene palabras escritas en un idioma olvidado. Si bien usa las mismas letras del alfabeto latino (a–z), el orden entre esas letras no es el mismo que en nuestro idioma.

A partir de una lista de palabras ordenadas lexicográficamente según ese idioma, tu objetivo es reconstruir el orden correcto de las letras.

Una palabra a es lexicográficamente más pequeña que una palabra b si se cumple una de las siguientes condiciones:

• La primera letra en la que difieren es menor en a que en b.
• No hay ningún índice i tal que a[i] != b[i] y a.length < b.length.

Deduce el orden de las letras en este idioma. Si el orden no es válido, devuelve una cadena vacía. Si hay varios órdenes de letras válidos, devuelve cualquiera de ellos.

Ejemplos

Input: ["z", "o"]
Output: "zo"
Explicación: De "z" y "o" deducimos que 'z' < 'o'.

Input: ["hrn", "hrf", "er", "enn", "rfnn"]
Output: "hernf"
Explicación:
- De "hrn" y "hrf" deducimos que 'n' < 'f'
- De "hrf" y "er" deducimos que 'h' < 'e'
- De "er" y "enn" deducimos que 'r' < 'n'
- De "enn" y "rfnn" deducimos que 'e' < 'r'
- Por lo que UNA posible solución es 'hernf'

Consideraciones

Se debe completar la lógica de la función

std::string& foreignDictionary(const std::vector<std::string>& words)
{
      //ToDo        
}

Debes buscar una solución con O(N + V + E) de tiempo y O(V + E) de espacio, donde N es la suma de las longitudes de todas las cadenas, V es el número de caracteres únicos (vértices) y E es el número de aristas.

• words es un vector de hasta 100 palabras.

• Cada palabra tiene al menos 1 y como máximo 100 letras.

• Las letras son minúsculas y van de 'a' a 'z'.

[giraudoignacio]

Profe acá mando lo que más o menos pude hacer, pero no sé como ver que sea O(N+V+E) de tiempo y O(V+E) de espacio

std::string& foreignDictionary(const std::vector<std::string>& words) {
    int alfabeto = 26; 
    std::vector<std::vector<int>> grafo(alfabeto); 
    std::vector<int> grados(alfabeto, 0); 
    std::vector<bool> vistas(alfabeto, false); 

    for (const std::string& palabra : words) {
        for (char letra : palabra) {
            vistas[letra - 'a'] = true;
        }
    }

    for (int i = 0; i + 1 < words.size(); i++) {
        const std::string& a = words[i];
        const std::string& b = words[i + 1];
        int largo = std::min(a.size(), b.size());
        bool diferencia = false;

        for (int j = 0; j < largo; j++) {
            if (a[j] != b[j]) {
                int inicio = a[j] - 'a';
                int fin = b[j] - 'a';

                bool existe = false;
                for (int adyacente : grafo[inicio]) {
                    if (adyacente == fin) {
                        existe = true;
                        break;
                    }
                }

                if (!existe) {
                    grafo[inicio].push(fin);
                    grados[fin]++;
                }

                diferencia = true;
                break;
            }
        }

        if (!diferencia && a.size() > b.size()) {
            return "";
        }
    }

    std::queue<int> cola;
    std::string resultado;
    
    for (int i = 0; i < alfabeto; ++i) { 
        if (vistas[i] && grados[i] == 0) {
            cola.push(i);
        }
    }
    
    while (!cola.empty()) {
        int actual = cola.front();
        cola.pop();
        char letra = actual + 'a';
        resultado += letra;

        for (int adyacente : grafo[actual]) {
            grados[adyacente]--;
            if (grados[adyacente] == 0) {
                cola.push(adyacente);
            }
        }
    }
    
    return resultado;
}

[EnzoFernandezz11]

#include <vector>
#include <queue>
#include <set>

std::vector<std::vector<int>> makeadj(const std::vector<std::string>& diccionario) {
   std::vector<std::vector<int>> adj(26); 

   for (size_t i = 0; i + 1 < diccionario.size(); ++i) {
       const std::string& a = diccionario[i];
       const std::string& b = diccionario[i + 1];
       size_t len = std::min(a.size(), b.size());
       for (size_t j = 0; j < len; ++j) {
           if (a[j] != b[j]  ) {
               int u = a[j] - 'a';
               int v = b[j] - 'a';
               adj[u].push_back(v);
               break; 
           }
       }
   }
   return adj;
}

std::string foreignDictionary(const std::vector<std::string>& words)
{
   auto adj = makeadj(words);

   std::set<int> letras;
   //guardo las letras que hay en el diccionario
   for (const auto& w : words)
       for (char c : w)
           letras.insert(c - 'a');

   //arranco con khan
   std::vector<int> indegree(26, 0);
   for (int i = 0; i < 26; i++) {
       for (auto it : adj[i]) {
           indegree[it]++;
       }
   }       

   //agrego a la cola solo las letras que estan y que son independientes
   std::queue<int> q;
   for (int i = 0; i < 26; i++) {
       if (letras.count(i) && indegree[i] == 0) {
           q.push(i);
       }
   }
   std::vector<int> result;
   while (!q.empty()) {
       int node = q.front();
       q.pop();
       result.push_back(node);

       for (auto it : adj[node]) {
           indegree[it]--;
           if (indegree[it] == 0)
               q.push(it);
       }
   }
   
   //convierto en string el resultado
   std::string orden;
   for (int idx : result) {
       orden += ('a' + idx);
   }
   return orden;
}