0269-alien-dictionary¶

Description¶

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.

If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".

Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there are multiple solutions, return any of them.

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 2:

Input: words = ["z","x"]
Output: "zx"

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters.

Solution(Python)¶

from collections import defaultdict
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        #  words = ["wrt","wrf","er","ett","rftt"]
        #  output  = "wertf"
        # 
        #  w -> r -> t
        #         -> f
        #   e-> r
        #   e       t  t
        #       r f t t
        #  w -> r f t
        #    e    
        #  if we create directed words with charcters and top sort gives the result
        #
        # Q1 how do i make directed graph
        #     since words are lexicograohically sorted 
        #    Compare two adjacent words until the first different character.
        #    compare adjacent words and create cnnection
        #  case 0 wrt wrf equal length or length of second words is longer
        #   w == w
        #   r == r
        #    t != f
        #    t -> f since t < f
        #    
        #  case 1 er  iterate until first word
        #  
        # Q1 finding top sort
        #    bfs use zero order first and then choose next order
        # Create graph with every unique character
        graph = {c: set() for word in words for c in word}
        indegree = {c: 0 for c in graph}

        # Build graph
        for i in range(len(words) - 1):
            word1 = words[i]
            word2 = words[i + 1]

            # Invalid prefix case
            if len(word1) > len(word2) and word1.startswith(word2):
                return ""

            for c1, c2 in zip(word1, word2):
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        indegree[c2] += 1
                    break

        # Topological Sort
        queue = deque([c for c in indegree if indegree[c] == 0])

        order = []

        while queue:
            node = queue.popleft()
            order.append(node)

            for nei in graph[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        if len(order) != len(graph):
            return ""

        return "".join(order)