Alien Dictionary hard

Problem Statement

There is a hidden word in an alien dictionary. You are given a list of words from the dictionary, where words are sorted lexicographically by the rules of this hidden alien dictionary. Return the order of the alphabet in this alien dictionary. If there is no solution, return "".

If there are multiple solutions, return any of them.

For Example: words = ["wrt","wrf","er","ett","rftt"] Output = "wertf"

words = ["z","x"] Output = "zx"

words = ["abc","ab"] Output = ""

Example 1

Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"

Example 2

Input: words = ["z","x"] Output: "zx"

Steps

1. Build the graph: Create a directed graph where each node represents a character. An edge from character 'a' to character 'b' indicates that 'a' comes before 'b' in the alien dictionary. We iterate through pairs of adjacent words in the input list. For each pair, we compare characters at the same index until we find a difference. If a difference is found, we add an edge from the character in the first word to the character in the second word.

2. Detect cycles: A cycle in the graph indicates a contradiction in the given word order (e.g., a < b and b < a). We use topological sort to check for cycles.

3. Topological Sort: If no cycles are present, perform a topological sort to determine the order of characters. Topological sort arranges nodes in a graph such that for every directed edge from node A to node B, node A appears before node B in the ordering. We use Kahn's algorithm for topological sorting.

4. Return the result: Concatenate the characters in the topological order to form the alien dictionary string. If a cycle is detected, return "".

Explanation

The algorithm uses graph theory to solve the problem. The words provide constraints on the character ordering. By building a graph representing these constraints, we can determine a valid ordering using topological sort. The absence of cycles ensures a consistent ordering exists.

Kahn's algorithm for topological sort works as follows:

• It counts the in-degree of each node (the number of incoming edges).
• It adds nodes with an in-degree of 0 to a queue.
• It processes nodes from the queue, decrementing the in-degree of their neighbors. When a neighbor's in-degree becomes 0, it's added to the queue.
• If the number of processed nodes equals the total number of nodes, a valid topological order has been found. Otherwise, a cycle exists.

Code

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>

using namespace std;

string alienOrder(vector<string>& words) {
    unordered_map<char, vector<char>> graph;
    unordered_map<char, int> inDegree;

    // Build the graph and calculate in-degrees
    for (const string& word : words) {
        for (char c : word) {
            inDegree[c] = 0;
        }
    }

    for (size_t i = 0; i < words.size() - 1; ++i) {
        const string& word1 = words[i];
        const string& word2 = words[i + 1];
        size_t minLen = min(word1.length(), word2.length());
        for (size_t j = 0; j < minLen; ++j) {
            if (word1[j] != word2[j]) {
                if (graph.find(word1[j]) == graph.end())
                   graph[word1[j]] = vector<char>();
                if (find(graph[word1[j]].begin(), graph[word1[j]].end(), word2[j]) == graph[word1[j]].end()){
                    graph[word1[j]].push_back(word2[j]);
                    inDegree[word2[j]]++;
                }
                break; 
            }
            if(j == minLen -1 && word1.length() > word2.length()) return ""; //check for invalid lexicographical order
        }
    }

    // Topological sort using Kahn's algorithm
    queue<char> q;
    for (auto const& [key, val] : inDegree) {
        if (val == 0) {
            q.push(key);
        }
    }

    string result = "";
    while (!q.empty()) {
        char c = q.front();
        q.pop();
        result += c;
        for (char neighbor : graph[c]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // Check for cycles
    if (result.length() != inDegree.size()) {
        return "";
    }

    return result;
}

Complexity

• Time Complexity: O(V + E), where V is the number of unique characters and E is the number of edges in the graph. Building the graph takes O(V + E) time. Topological sort also takes O(V + E) time.

• Space Complexity: O(V + E), to store the graph and in-degrees. In the worst case (a fully connected graph), E could be O(V^2).