Back to DSA

Alien Dictionary

hard
Acceptance: 37%
GraphsTopological Sort

An unknown language uses familiar English letters but in a different alphabetical order. Given a list of words sorted according to this unknown ordering, deduce the order of the letters. If the given ordering is contradictory, return an empty string. If multiple valid orderings exist, return any one of them.

Examples

Example 1:
Input:words = ["ba","bc","ac","cab"]
Output:"bac"
Explanation: From ba < bc: a < c. From bc < ac: b < a. From ac < cab: a < c (already known). Order: b, a, c.
Example 2:
Input:words = ["x","y","x"]
Output:""
Explanation: x < y and y < x is contradictory.

Hints

Related Problems

Clone GraphmediumPacific Atlantic Water FlowmediumRotting OrangesmediumWalls and GatesmediumShortest Path in Binary Matrixmedium
00:00
import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) { graph.putIfAbsent(c, new HashSet<>()); inDegree.putIfAbsent(c, 0); }
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (graph.get(w1.charAt(j)).add(w2.charAt(j))) {
                        inDegree.merge(w2.charAt(j), 1, Integer::sum);
                    }
                    break;
                }
            }
        }
        Queue<Character> queue = new LinkedList<>();
        for (var e : inDegree.entrySet()) if (e.getValue() == 0) queue.offer(e.getKey());
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);
            for (char next : graph.get(c)) {
                inDegree.merge(next, -1, Integer::sum);
                if (inDegree.get(next) == 0) queue.offer(next);
            }
        }
        return sb.length() == inDegree.size() ? sb.toString() : "";
    }
}
Time complexityO(C)
Space complexityO(1)