alien_dictionary

  1from collections import Counter, defaultdict, deque
  2
  3
  4# @leet start
  5class Solution:
  6    def alienOrder(self, words: list[str]) -> str:
  7        """
  8        This question asks us to return an ordering of characters given a set
  9        of sorted words.
 10
 11        First, we describe the relation between the characters. We do this by
 12        extracting the first character of each pair that doesn't match, and
 13        noting that the left side char comes before the right side.
 14
 15        For these words:
 16
 17        wrt
 18        wrf
 19        er
 20        ett
 21        rftt
 22
 23        the pairs would be (wrt, wrf), (wrf, er), (er, ett), (ett, rftt).
 24
 25        For each pair, we want to find which ones come before, so:
 26
 27        (wrt, wrf) = t -> f (since wr are the same, t and f are the first differing
 28        characters, and t is on the left side of our pair, so t comes before f).
 29        (wrf, er) = w -> e (since w and e don't match, and w is on the left).
 30        (er, ett) = r -> t (since e matches for both, and r is on the left).
 31        (ett, rftt) = e -> r (since e must come before r).
 32
 33        As well, we want to create an indegree map that counts how man indegrees
 34        each node has. For this graph:
 35
 36        t -> f
 37        w -> e
 38        r -> t
 39        e -> r
 40
 41        The indegrees are:
 42
 43        r -> 1
 44        t -> 1
 45        f -> 1
 46        e -> 1
 47        w -> 0
 48
 49        In this case, we find any node with indegree 0 and do a topological sort.
 50        So in the above case, we visit w, add it to our output, and then check
 51        if its children, in this case, e are visitable.
 52
 53        e has an indegree of 1, so after w is visited, it is visitable, so
 54        we visit e.
 55
 56        Then, e allows us to visit r, which also has an indegree of 1, so after
 57        visiting e, r is visitable.
 58
 59        Then we visit r, which has a child of t, and we can visit t after visiting
 60        r because it has an indegree of 1.
 61
 62        Then we visit t, which allows us to visit f.
 63
 64        This allows us to construct the string "wertf", which is the only valid
 65        ordering for this example, but other examples may have more orderings.
 66
 67        We make sure that we've counted every char in the original set of words
 68        before returning the joined string.
 69
 70        """
 71        adj_list = defaultdict(set)
 72        indegrees = Counter({c: 0 for word in words for c in word})
 73
 74        for l, r in zip(words, words[1:]):
 75            for c, d in zip(l, r):
 76                if c != d:
 77                    if d not in adj_list[c]:
 78                        adj_list[c].add(d)
 79                        indegrees[d] += 1
 80                    break
 81            else:
 82                if len(r) < len(l):
 83                    return ""
 84
 85        output = []
 86        q = deque([c for c in indegrees if indegrees[c] == 0])
 87        while q:
 88            c = q.popleft()
 89            output.append(c)
 90            for d in adj_list[c]:
 91                indegrees[d] -= 1
 92                if indegrees[d] == 0:
 93                    q.append(d)
 94
 95        if len(output) < len(indegrees):
 96            return ""
 97        return "".join(output)
 98
 99
100# @leet end
101
102
103def test():
104    assert 2 + 2 == 4