Alien Dictionary

1package pkg5leetcode.blind75;2 3/*4 * Alien Dictionary | LC 2695 * APPROACH: Build char graph from sorted words; topological sort or cycle check.6 * COMPLEXITY: Time O(C) total chars, Space O(1) alphabet7 */8import java.util.*;9 10public class blind75_LC269AlienDictionary {11    static String alienOrder(String[] words) {12        Map<Character, Set<Character>> adj = new HashMap<>();13        Map<Character, Integer> indeg = new HashMap<>();14        for (String w : words)15            for (char c : w.toCharArray()) {16                adj.putIfAbsent(c, new HashSet<>());17                indeg.putIfAbsent(c, 0);18            }19        for (int i = 0; i < words.length - 1; i++) {20            String w1 = words[i], w2 = words[i + 1];21            if (w1.length() > w2.length() && w1.startsWith(w2)) return "";22            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {23                char c1 = w1.charAt(j), c2 = w2.charAt(j);24                if (c1 != c2) {25                    if (!adj.get(c1).contains(c2)) {26                        adj.get(c1).add(c2);27                        indeg.put(c2, indeg.get(c2) + 1);28                    }29                    break;30                }31            }32        }33        Deque<Character> q = new ArrayDeque<>();34        for (char c : indeg.keySet()) if (indeg.get(c) == 0) q.add(c);35        StringBuilder sb = new StringBuilder();36        while (!q.isEmpty()) {37            char c = q.poll();38            sb.append(c);39            for (char nb : adj.get(c)) {40                int d = indeg.get(nb) - 1;41                indeg.put(nb, d);42                if (d == 0) q.add(nb);43            }44        }45        return sb.length() == indeg.size() ? sb.toString() : "";46    }47 48    public static void main(String[] args) {49        check(alienOrder(new String[]{"wrt", "wrf", "er", "ett", "rftt"}).equals("wertf"), "case1");50        check(alienOrder(new String[]{"z", "x"}).equals("zx"), "case2");51        System.out.println("all tests passed");52    }53 54    static void check(boolean cond, String name) {55        if (!cond) throw new AssertionError("FAILED: " + name);56        System.out.println("  PASS " + name);57    }58}