words · neighbours compared
Letter graph · badge = indegree
q · indegree 0
res
public String foreignDictionary(String[] words) { Map<Character, Set<Character>> adj = new LinkedHashMap<>(); Map<Character, Integer> indegree = new LinkedHashMap<>(); for (String w : words) { for (char c : w.toCharArray()) { adj.putIfAbsent(c, new LinkedHashSet<>()); indegree.putIfAbsent(c, 0); } } for (int i = 0; i < words.length - 1; i++) { String w1 = words[i]; String w2 = words[i + 1]; int minLen = Math.min(w1.length(), w2.length()); if (w1.length() > w2.length() && w1.startsWith(w2)) { return ""; } for (int j = 0; j < minLen; j++) { char a = w1.charAt(j); char b = w2.charAt(j); if (a != b) { // first difference decides if (adj.get(a).add(b)) { indegree.put(b, indegree.get(b) + 1); } break; } } } Deque<Character> q = new ArrayDeque<>(); for (char c : indegree.keySet()) { if (indegree.get(c) == 0) { q.add(c); } } StringBuilder res = new StringBuilder(); while (!q.isEmpty()) { char c = q.poll(); res.append(c); for (char nei : adj.get(c)) { indegree.put(nei, indegree.get(nei) - 1); if (indegree.get(nei) == 0) { q.add(nei); } } } if (res.length() != indegree.size()) { return ""; // a cycle kept some letters waiting } return res.toString();}
- w1, w2
- —
- j
- —
- char
- —
- edges
- 0
- res
- ""
Why it works
- Brute force tries every ordering of the k letters and checks the word list against it: O(k! · C).
- Only neighbouring words carry information, and only at their first differing column:
"wrt"before"wrf"saystcomes beforef, nothing more. Comparing non-neighbours adds nothing new, because sorted order is transitive. - The order is a topological sort of those "before" edges. Kahn's algorithm repeatedly takes a letter with no remaining predecessors (indegree 0). Every letter and edge is handled once: O(C) for the comparisons, O(1) space for at most 26 letters and 26² edges.
- Pitfalls: a longer word before its own prefix (
"abc","ab") is impossible, return"". A cycle (z<x<z) leaves letters with indegree > 0 forever, sorescomes up short. Count a repeated edge only once, or its indegree never reaches 0. - Related: Course Schedule II (210) is the same Kahn loop on given edges. Several orders can be valid; any one is accepted.