#269

Alien Dictionary

hard· Advanced Graphsruns: 0

There is a new alien language that uses the English alphabet, but the order of letters is unknown. You are given a list of strings words from this language's dictionary, sorted lexicographically. Derive the order of letters in this language. Return any valid string of unique letters representing this order, or empty string if no valid order exists.

wpm 0acc 100%time 0:000 / 1067

from collections import defaultdict, deque

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        graph = defaultdict(set)
        indegree = {c: 0 for word in words for c in word}
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""
            for j in range(min_len):
                if w1[j] != w2[j]:
                    if w2[j] not in graph[w1[j]]:
                        graph[w1[j]].add(w2[j])
                        indegree[w2[j]] += 1
                    break
        queue = deque([c for c in indegree if indegree[c] == 0])
        result = []
        while queue:
            c = queue.popleft()
            result.append(c)
            for neighbor in graph[c]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)
        return "".join(result) if len(result) == len(indegree) else ""

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.