Alien Dictionary
The drill: A list of words is claimed to already be sorted by some unknown alphabet's rules. Recover a letter ordering consistent with that claim, or report that no ordering could have produced this list.
A list of words arrives in a fixed order, and the claim is that this order matches dictionary order under some alien alphabet whose letter-to-letter ranking is unknown.
The job is to recover one letter ordering that would make the list's order valid, using only the information adjacent words in the list can reveal. A contradictory list — one no single ordering could have produced — has to be reported instead.
One case invalidates any ordering outright, alphabet aside: a longer word sitting immediately before its own prefix can never be sorted correctly, no matter how the letters rank.
- word count can run into the low thousands, lowercase letters only
- letter ordering only needs to include letters that actually appear
- several orderings can be valid; returning any one of them is fine
- a word immediately followed by its own proper prefix makes the input invalid
- a cycle among the inferred letter rules also makes the input invalid
HINT 1 THE NUDGE
Only ADJACENT words carry information — the first pair of words that differ pins down exactly one letter-before-letter fact. Everything else is noise you don't need to look at.
HINT 2 THE STRUCTURE
Every such fact is an edge: this letter precedes that letter. Once every adjacent pair has contributed its edge, the puzzle stops being about words entirely — it's about ordering the nodes of a graph so every edge points forward.
HINT 3 ONE STEP FROM THE ANSWER
Topologically sort the letter graph. Watch for the one edge case that isn't really a graph problem: a longer word sitting directly before its own prefix can never be valid, no matter the alphabet.
Compare adjacent words: ab vs ac gives b before c; ac vs b gives a before b. Count in-degrees, then peel zero-indegree letters.
class Solution:
def alienOrder(self, words: List[str]) -> str:
indegree = {c: 0 for w in words for c in w}
graph = collections.defaultdict(set)
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minlen = min(len(w1), len(w2))
found = False
for j in range(minlen):
if w1[j] != w2[j]:
if w2[j] not in graph[w1[j]]:
graph[w1[j]].add(w2[j])
indegree[w2[j]] += 1
found = True
break
if not found and len(w1) > len(w2):
return ""
queue = collections.deque([c for c in indegree if indegree[c] == 0])
order = []
while queue:
c = queue.popleft()
order.append(c)
for nxt in graph[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
if len(order) < len(indegree):
return ""
return "".join(order)class Solution:
def alienOrder(self, words: List[str]) -> str:
letters = set()
for w in words:
letters.update(w)
edges = set()
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minlen = min(len(w1), len(w2))
found = False
for j in range(minlen):
if w1[j] != w2[j]:
edges.add((w1[j], w2[j]))
found = True
break
if not found and len(w1) > len(w2):
return ""
letters = sorted(letters)
for perm in itertools.permutations(letters):
idx = {c: i for i, c in enumerate(perm)}
if all(idx[a] < idx[b] for a, b in edges):
return "".join(perm)
return ""class Solution {
public String alienOrder(String[] words) {
Map<Character, Integer> indegree = new HashMap<>();
for (String w : words) {
for (char c : w.toCharArray()) indegree.putIfAbsent(c, 0);
}
Map<Character, Set<Character>> graph = new HashMap<>();
for (int i = 0; i + 1 < words.length; i++) {
String w1 = words[i], w2 = words[i + 1];
int minLen = Math.min(w1.length(), w2.length());
boolean found = false;
for (int j = 0; j < minLen; j++) {
char a = w1.charAt(j), b = w2.charAt(j);
if (a != b) {
Set<Character> nbrs = graph.computeIfAbsent(a, x -> new HashSet<>());
if (nbrs.add(b)) {
indegree.put(b, indegree.get(b) + 1);
}
found = true;
break;
}
}
if (!found && w1.length() > w2.length()) return "";
}
Deque<Character> queue = new ArrayDeque<>();
for (Map.Entry<Character, Integer> e : indegree.entrySet()) {
if (e.getValue() == 0) queue.add(e.getKey());
}
StringBuilder order = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
order.append(c);
for (char nxt : graph.getOrDefault(c, Collections.emptySet())) {
indegree.put(nxt, indegree.get(nxt) - 1);
if (indegree.get(nxt) == 0) queue.add(nxt);
}
}
if (order.length() < indegree.size()) return "";
return order.toString();
}
}class Solution {
public String alienOrder(String[] words) {
Set<Character> letters = new TreeSet<>();
for (String w : words) {
for (char c : w.toCharArray()) letters.add(c);
}
Set<int[]> edgesRaw = new HashSet<>();
List<char[]> edges = new ArrayList<>();
for (int i = 0; i + 1 < words.length; i++) {
String w1 = words[i], w2 = words[i + 1];
int minLen = Math.min(w1.length(), w2.length());
boolean found = false;
for (int j = 0; j < minLen; j++) {
if (w1.charAt(j) != w2.charAt(j)) {
edges.add(new char[] { w1.charAt(j), w2.charAt(j) });
found = true;
break;
}
}
if (!found && w1.length() > w2.length()) return "";
}
List<Character> letterList = new ArrayList<>(letters);
char[] perm = new char[letterList.size()];
boolean[] used = new boolean[letterList.size()];
String result = permute(letterList, perm, used, 0, edges);
return result == null ? "" : result;
}
private String permute(List<Character> letters, char[] perm, boolean[] used, int depth, List<char[]> edges) {
if (depth == letters.size()) {
if (satisfies(perm, edges)) return new String(perm);
return null;
}
for (int i = 0; i < letters.size(); i++) {
if (!used[i]) {
used[i] = true;
perm[depth] = letters.get(i);
String r = permute(letters, perm, used, depth + 1, edges);
used[i] = false;
if (r != null) return r;
}
}
return null;
}
private boolean satisfies(char[] perm, List<char[]> edges) {
Map<Character, Integer> idx = new HashMap<>();
for (int i = 0; i < perm.length; i++) idx.put(perm[i], i);
for (char[] e : edges) {
if (idx.get(e[0]) >= idx.get(e[1])) return false;
}
return true;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED