Sweaty Imposter

Alien Dictionary

HardTopological SortBlind 75SeniorOpen on LeetCodeUpdated

An alien language uses lowercase English letters in an unknown order. You're given a list of words sorted by that order: words compare at their first differing letter, and a word that is a prefix of another comes first. Return a string of every distinct letter in the words, in an order consistent with the list; if several fit, return any. If none fits (the list contradicts itself, or a word comes before its own prefix, like "abc" before "ab"), return "".

Examples

words = ["wrt","wrf","er","ett","rftt"] returns "wertf"

wertf
An arrow means the first letter comes earlier in the alphabet. Each arrow comes from one pair of neighboring words.

wrt and wrf first differ at t and f, so t comes before f. Likewise wrf and er give w before e, er and ett give r before t, and ett and rftt give e before r. Chaining these gives w, e, r, t, f.

words = ["z","x"] returns "zx"

The two words differ at their first letter, and z is listed first, so z comes before x.

words = ["z","x","z"] returns ""

The first pair puts z before x, and the second pair puts x before z. Both can't hold, so no order exists.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100

Hints

Hint 1

Where does the relative order of two letters become visible in a sorted word list?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Compare each pair of neighboring words. Their first differing position gives one fact, the earlier word's letter before the later word's, and nothing after it says anything. Record each fact once as a directed edge between letters, then run Kahn's algorithm, repeatedly outputting a letter with no incoming edges left. If some letters never come out, the facts form a cycle, so return "". A word followed by its own proper prefix returns "" at once. O(C) time, C = total characters; O(1) extra space for at most 26 letters.

Time

O(C)

Space

O(1)

Pitfall

A word followed by its own prefix, like "abc" then "ab", has no differing letter and so adds no edge, yet the list is invalid. Check for it explicitly. Also stop at the first differing position; later letters carry no ordering information.

Solutions

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> indeg = new HashMap<>();
        for (String w : words) for (char c : w.toCharArray()) {
            graph.putIfAbsent(c, new HashSet<>());
            indeg.putIfAbsent(c, 0);
        }
        for (int i = 0; i + 1 < words.length; i++) {
            String a = words[i], b = words[i + 1];
            if (a.length() > b.length() && a.startsWith(b)) return "";
            int len = Math.min(a.length(), b.length());
            for (int j = 0; j < len; j++) {
                char x = a.charAt(j), y = b.charAt(j);
                if (x != y) {
                    if (graph.get(x).add(y)) indeg.merge(y, 1, Integer::sum);
                    break;
                }
            }
        }
        Deque<Character> queue = new ArrayDeque<>();
        for (var e : indeg.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 nb : graph.get(c)) {
                indeg.merge(nb, -1, Integer::sum);
                if (indeg.get(nb) == 0) queue.offer(nb);
            }
        }
        return sb.length() == indeg.size() ? sb.toString() : "";
    }
}
Drill This