LC 0269 [H] Alien Dictionary - ALawliet/algorithms GitHub Wiki

• build adjacency list of neighbors for a directed graph with count of indegrees, break after first char diff
• if no break then edge case to bail early if we get a prefix after a word (contradiction) because it cannot be decoded
• topological sort

---

class Solution:
    def toposort(self, adj, indeg):
        order = []
        Q = deque([c for c in indeg if indeg[c] == 0])
        while Q:
            u = Q.popleft()
            order.append(u)
            for v in adj[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    Q.append(v)
        return order
    
    def alienOrder(self, words: List[str]) -> str:
        adj = defaultdict(set)
        indeg = {c: 0 for w in words for c in w}

        for w1, w2 in zip(words, words[1:]):
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in adj[c1]:
                        adj[c1].add(c2)
                        indeg[c2] += 1
                    break
            else:
                if not len(w1) <= len(w2): return ''
                
        order = self.toposort(adj, indeg)

        if len(order) != len(indeg): return ''
        return ''.join(order)

from queue import Queue

class Solution:
    def alienOrder(self, words: List[str]) -> str:
    
        # Step 0: create data structures + the indegree of each unique letter to 0.
        neighbors = defaultdict(set)
        indegree = Counter({c:0 for word in words for c in word})

        # Step 1: We need to populate adjlist of neighbors and indegree.
        # For each pair of adjacent words...
        for w1, w2 in zip(words, words[1:]):
            for c1, c2 in zip(w1, w2):
                if c1 != c2:
                    if c2 not in neighbors[c1]:
                        neighbors[c1].add(c2)
                        indegree[c2] += 1
                    break # first diff
            else: # Check that second word isn't a prefix of first because prefixes come first so if abc,ab can't find valid ordering
                if not len(w1) <= len(w2): return ''

        # Step 2: We need to repeatedly pick off nodes with an indegree of 0.
        output = []
        Q = Queue()
        [Q.put(c) for c in indegree if indegree[c] == 0]   
        while not Q.empty():
            node = Q.get()
            output.append(node)
            for neighbor in neighbors[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    Q.put(neighbor)

        # If not all letters are in output, that means there was a cycle and so
        # no valid ordering. Return '' as per the problem description.
        if len(output) < len(indegree): return ''
        # Otherwise, convert the ordering we found into a string and return it.
        return ''.join(output)