Skip to content
AI360Xpert
Back to Advanced Graphs
Hard

Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you. You are given a list of strings `words` from the alien language's dictionary, where the strings in `words` are **sorted lexicographically** by the rules of this new language. Return a string of the unique letters in the new alien language sorted in **lexicographically increasing order** by the new language's rules. If there is no solution, return `""`. If there are multiple solutions, return **any of them**.

Examples

Input:words = ["wrt","wrf","er","ett","rftt"]
Output:"wertf"
From "wrt" and "wrf", we know 't' comes before 'f'. From "wrt" and "er", we know 'w' comes before 'e'. From "er" and "ett", we know 'r' comes before 't'. From "ett" and "rftt", we know 'e' comes before 'r'. This gives us the order w -> e -> r -> t -> f.
Input:words = ["z","x"]
Output:"zx"
From "z" and "x", we know 'z' comes before 'x'.
Input:words = ["z","x","z"]
Output:""
The order is invalid, so return "".

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of only lowercase English letters.

Topological Sort (Kahn's Algorithm)

Approach

This problem can be modeled as finding a topological ordering of a directed graph. The nodes are the unique characters in the words, and the directed edges represent the ordering between characters. First, we extract the ordering rules by comparing adjacent words in the given list. For any two adjacent words, we find the first character where they differ. This difference tells us that the character from the first word must come before the character from the second word in the alien alphabet, giving us a directed edge. Also, we must handle the edge case where a longer word appears before its prefix (like "abc" before "ab"); since the words are sorted, this is an invalid ordering, and we can immediately return an empty string. Once we have our graph (adjacency list) and the in-degrees (number of incoming edges) for each character, we can use Kahn's algorithm for topological sorting. We use a queue and start by adding all characters with an in-degree of 0. We repeatedly remove a character from the queue, append it to our result string, and decrease the in-degree of all its neighbors. If a neighbor's in-degree reaches 0, we add it to the queue. Finally, if the result string contains all the unique characters, we return it. If it doesn't, it means there is a cycle in the graph (a contradiction in the ordering), and we return an empty string.

Complexity Analysis

Time Complexity
O(C)
Space Complexity
O(1) or O(U + min(U^2, N))

C is the total length of all the words in the input list, added together. We compare each word to the next, which takes at most O(C) time. U is the number of unique characters. Since U <= 26, the space complexity and time to do topological sort are bounded by a constant O(1).

Solution.java
class Solution {    public String alienOrder(String[] words) {        Map<Character, List<Character>> adjList = new HashMap<>();        Map<Character, Integer> counts = new HashMap<>();                // Initialize graphs and in-degree counts        for (String word : words) {            for (char c : word.toCharArray()) {                counts.put(c, 0);                adjList.put(c, new ArrayList<>());            }        }                // Build the graph        for (int i = 0; i < words.length - 1; i++) {            String word1 = words[i];            String word2 = words[i + 1];                        // Check that word2 is not a prefix of word1            if (word1.length() > word2.length() && word1.startsWith(word2)) {                return "";            }                        // Find the first non-matching character            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {                if (word1.charAt(j) != word2.charAt(j)) {                    adjList.get(word1.charAt(j)).add(word2.charAt(j));                    counts.put(word2.charAt(j), counts.get(word2.charAt(j)) + 1);                    break;                }            }        }                // Topological sort using BFS (Kahn's Algorithm)        StringBuilder sb = new StringBuilder();        Queue<Character> queue = new LinkedList<>();                for (Character c : counts.keySet()) {            if (counts.get(c).equals(0)) {                queue.add(c);            }        }                while (!queue.isEmpty()) {            Character c = queue.remove();            sb.append(c);            for (Character next : adjList.get(c)) {                counts.put(next, counts.get(next) - 1);                if (counts.get(next).equals(0)) {                    queue.add(next);                }            }        }                if (sb.length() < counts.size()) {            return "";        }        return sb.toString();    }}