LeetCode Solution 269 - Alien Dictionary (Topological Sort)

Problem Statement:

There is a new alien language that uses the English alphabet, but the order of letters is unknown. Given a list of words from the alien dictionary in lexicographical order, derive the order of letters in the language.

If the order is invalid or inconsistent, return an empty string.

Example:

Input:

words = ["wrt", "wrf", "er", "ett", "rftt"]

Output: "wertf"

Explanation: The correct character order is: 'w' -> 'e' -> 'r' -> 't' -> 'f'.

---

Optimal Approach: Graph + Topological Sorting (Kahn's Algorithm)

Approach Explanation:

• Construct a directed graph from the given words.
• Use in-degree tracking to determine the character order.
• Perform a topological sort using BFS (Kahn's Algorithm).

C++ Solution:

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> graph;
        unordered_map<char, int> inDegree;
        for (auto &word : words) for (char c : word) inDegree[c] = 0;
        
        for (int i = 0; i < words.size() - 1; i++) {
            string w1 = words[i], w2 = words[i+1];
            int minLen = min(w1.size(), w2.size());
            if (w1.size() > w2.size() && w1.substr(0, minLen) == w2) return "";
            for (int j = 0; j < minLen; j++) {
                if (w1[j] != w2[j]) {
                    if (!graph[w1[j]].count(w2[j])) {
                        graph[w1[j]].insert(w2[j]);
                        inDegree[w2[j]]++;
                    }
                    break;
                }
            }
        }
        
        queue<char> q;
        for (auto &[c, deg] : inDegree) if (deg == 0) q.push(c);
        string result;
        while (!q.empty()) {
            char c = q.front(); q.pop();
            result += c;
            for (char neighbor : graph[c]) {
                if (--inDegree[neighbor] == 0) q.push(neighbor);
            }
        }
        return result.size() == inDegree.size() ? result : "";
    }
};

---

Step-by-Step Execution:

1. Graph Construction: Build adjacency list based on character precedence.
2. In-degree Calculation: Track incoming edges for each character.
3. Topological Sort (BFS): Process characters with zero in-degree and maintain order.
4. Validation: Ensure all characters are included; detect cycles.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Drawback
Brute Force	O(N²)	O(1)	Inefficient comparison of all pairs
DFS Topological Sort	O(N)	O(N)	Similar efficiency, but more complex to implement
Sorting-Based Approach	O(N log N)	O(N)	Does not handle all cases correctly

Why BFS (Kahn’s Algorithm) is the Best?

• Handles cyclic dependencies efficiently.
• Ensures lexicographical order by processing nodes with zero in-degree.
• Optimized for large inputs with O(N + E) complexity.

---

Complexity Analysis:

• Time Complexity: O(N + E), where N is the number of unique characters and E is the number of edges.
• Space Complexity: O(N + E), for storing the graph and in-degree counts.

---

Conclusion:

• Best Approach: Graph + Topological Sort using BFS.
• Key Idea: Process characters based on precedence using Kahn’s Algorithm.
• Efficiency: O(N + E) time complexity with optimal space usage.
• Alternative Practice Problems:
  • Course Schedule
  • Sequence Reconstruction
  • Word Ladder

This solution efficiently determines the order of letters in an alien dictionary using topological sorting, making it the best approach for this problem.