Problem statement

https://leetcode.com/problems/alien-dictionary/

Solution

The idea is to use topological sort. Let us traverse all pairs of adjacent words, for example if we have aylksga and aymst, we can state that l must go before m. Also we need to check that if we have case like agsag and ags, than no matter what happens else, answer will always be false. After we create our connections graph, we need to perform dfs with $3$ colors for all components. In the end if we found loop, return "", and if we did not, return reversed order.

Complexity

Time complexity is $O(m)$, where $m$ is total length of all words, this part will be bigger than dfs part. Space complexity is $O(d + \min(d^2, n))$, where $d$ is the size of alphabet and $n$ is lenght of words.

Code

class Solution:
    def alienOrder(self, words):
        def dfs(node):
            if visited[node] == 1:
                self.FoundCycle = 1
            if visited[node] == 0:
                visited[node] = 1
                for neib in graph[node]: dfs(neib)
                visited[node] = 2
                self.ans += node
        
        exist, visited = set("".join(words)), Counter()
        self.ans, self.FoundCycle = "", 0
        graph = defaultdict(list)
        
        for w1, w2 in zip(words, words[1:]):
            for i, j in zip(w1, w2):
                if i != j:
                    graph[i].append(j)
                    break
            if w1.startswith(w2) and w1 != w2: return ""

        for i in exist:
            if visited[i] == 0:   dfs(i)

        if self.FoundCycle == 1:   return "" 
        return self.ans[::-1]