Alien Dictionary GFG

#leetcode #dsa/graphs

Question

A new alien language uses the English alphabet, but the order of letters is unknown. You are given a list of words[] from the alien language’s dictionary, where the words are claimed to be sorted lexicographically according to the language’s rules.

Your task is to determine the correct order of letters in this alien language based on the given words. If the order is valid, return a string containing the unique letters in lexicographically increasing order as per the new language's rules. If there are multiple valid orders, return any one of them.

However, if the given arrangement of words is inconsistent with any possible letter ordering, return an empty string ("").

A string a is lexicographically smaller than a string b if, at the first position where they differ, the character in a appears earlier in the alien language than the corresponding character in b. If all characters in the shorter word match the beginning of the longer word, the shorter word is considered smaller.

Note: Your implementation will be tested using a driver code. It will print true if your returned order correctly follows the alien language’s lexicographic rules; otherwise, it will print false.

Examples:

Input: words[] = ["baa", "abcd", "abca", "cab", "cad"]
Output: true
Explanation: A possible corrct order of letters in the alien dictionary is "bdac".
The pair "baa" and "abcd" suggests 'b' appears before 'a' in the alien dictionary.
The pair "abcd" and "abca" suggests 'd' appears before 'a' in the alien dictionary.
The pair "abca" and "cab" suggests 'a' appears before 'c' in the alien dictionary.
The pair "cab" and "cad" suggests 'b' appears before 'd' in the alien dictionary.
So, 'b' → 'd' → 'a' → 'c' is a valid ordering.

Input: words[] = ["caa", "aaa", "aab"]
Output: true
Explanation: A possible corrct order of letters in the alien dictionary is "cab".The pair "caa" and "aaa" suggests 'c' appears before 'a'.
The pair "aaa" and "aab" suggests 'a' appear before 'b' in the alien dictionary.
So, 'c' → 'a' → 'b' is a valid ordering.

Input: words[] = ["ab", "cd", "ef", "ad"]
Output: ""
Explanation: No valid ordering of letters is possible.
The pair "ab" and "ef" suggests "a" appears before "e".
The pair "ef" and "ad" suggests "e" appears before "a", which contradicts the ordering rules.

**Constraints:
**1 ≤ words.length ≤ 5001 ≤ words[i].length ≤ 100words[i] consists only of lowercase English letters.

Try more examples

Approach 1: Kahn's Algorithm BFS

Intuition

Algorithm

Code

class Solution {
public:
    string findOrder(vector<string>& words) {
        unordered_map<char, vector<char>> adj;

        // Step 1: Add all characters
        for (string& word : words) {
            for (char c : word) {
                if (!adj.count(c)) {
                    adj[c] = {};
                }
            }
        }

        // Step 2: Build edges
        for (int i = 0; i < words.size() - 1; i++) {
            string s1 = words[i];
            string s2 = words[i + 1];
            int minLength = min(s1.size(), s2.size());
            bool found = false;

            for (int j = 0; j < minLength; j++) {
                if (s1[j] != s2[j]) {
                    adj[s1[j]].push_back(s2[j]);
                    found = true;
                    break;
                }
            }

            if (!found && s1.size() > s2.size()) {
                return "";
            }
        }

        // Step 3: Indegree calculation
        unordered_map<char, int> indegree;
        for (auto& entry : adj) {
            char node = entry.first;
            for (char neighbor : entry.second) {
                indegree[neighbor]++;
            }
        }

        // Step 4: Queue for nodes with 0 indegree
        queue<char> q;
        for (auto& entry : adj) {
            char node = entry.first;
            if (indegree[node] == 0) {
                q.push(node);
            }
        }

        // Step 5: Kahn's algorithm
        string ans;
        while (!q.empty()) {
            char node = q.front();
            q.pop();
            ans += node;

            for (char neighbor : adj[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return ans.size() == adj.size() ? ans : "";
    }
};

Complexity Analysis