269.Alien_Dictionary(Hard).md

269. Alien Dictionary (Hard)

Date and Time: Sep 27, 2024, (EST)

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

Question:

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.

Walk-through:

1. Build an adj dictionary with list, and we add the difference between each two words as a pair, and add adj[w1[j]].add(w2[j]).

2. Run DFS on each c in adj, which is the key.

Python Solution:

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Topological sort by DFS post order
        adj = {c: set() for w in words for c in w}
        # Compare each two words a pair, add difference into w1 set()
        for i in range(len(words)-1):
            w1, w2 = words[i], words[i+1]
            minLen = min(len(w1), len(w2))
            if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
                return ""
            for j in range(minLen):
                if w1[j] != w2[j]:
                    adj[w1[j]].add(w2[j])
                    break
        
        visited, res = {}, []
        def dfs(c):
            if c in visited:
                return visited[c]
            visited[c] = True
            for nei in adj[c]:
                if dfs(nei):
                    return True
            visited[c] = False
            res.append(c)
        
        for c in adj:
            if dfs(c):
                return ""
                
        res.reverse()
        return "".join(res)

Time Complexity: $O()$
Space Complexity: $O()$