DiffPush Tier Graphs · Topo Sort Problems O(N * L) · O(k)
Signals interception recovered a sorted word list from an alien civilisation using the first k earth-equivalent letters. Comparing each neighbouring word pair at its first differing position reveals one before-the-other fact; chaining all those facts should yield one total letter precedence — provided the intercepted list isn't self-contradictory.
Input: A list dict of N words sorted by the alien alphabet, and an integer k — the number of letters (a..) in use.
Output: Return the alien character order as a string of k lowercase letters.
1 <= N <= 10^31 <= k <= 261 <= word length <= 10^2All words consist only of the first k lowercase lettersInput: {"dict":["baa","abcd","abca","cab","cad"],"k":4}
Output: "bdac"
baa<abcd pins b<a; abcd<abca pins d<c; abca<cab pins a<c — topologically b,d,a,c.
Input: {"dict":["wrt","wrf","er","ett","rftt"],"k":5}
Output: "wertf"
The five comparisons chain into the order w, e, r, t, f.