LC 269 - 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.

Links

Question here and solution here

Solution

concept

This question is actually a graph problem that needs topological sort. We need to arrange the problem into a graph by choosing the right representation of the adjacency list. For example, focus on the green example below for A, B, B: we have to compare the word and digit and get the first different char and then from there construct the adjacency list. We then can use the same technique in 210. Course Schedule II for topological sorting. Take note that this is post-order DFS and this is the way for topological sort, we just need to reverse the answer in the end. Note that we do not need to reverse in 210. Course Schedule II because in that question we actually need to return the answer in reverse as by the question.

code

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj_list = {c:set() for w in words for c in w}
		# construct adj list
		# key: char
        # val: set of char that is lexicographically behind the key according to words given
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i+1]
            min_len = min(len(w1), len(w2))
            if w1[:min_len] == w2[:min_len] and len(w1) > len(w2): # and also w1 is before w2 in pos
                return ""
            for j in range(min_len):
                if w1[j] != w2[j]:
                    adj_list[w1[j]].add(w2[j])
                    break
        
        ans = []
        visited = set() # current path
        processed = set() # already added into ans

        def dfs(c):
            if c in visited:
                return False # detected cycle
            if c in processed:
                return True # processed 

            visited.add(c)
            for nei in adj_list[c]:
                if not dfs(nei):
                    return False # found cycle
            visited.remove(c)
            processed.add(c)
            ans.append(c)
            return True

        for c in adj_list.keys():
            if not dfs(c):
                return ""
        
        ans.reverse()

        return "".join(ans)
        
        
class NeetSolution:
	"""
	mostly same as above
	but he only used one set to represent 3 state
	"""
    def foreignDictionary(self, words: List[str]) -> str:
        adj = {c: set() for w in words for c in w}

        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
		# False: processed; True: visited and it is in current path -> lead to cyclic; Not found: not visited yet
        visited = {}
        res = []

        def dfs(char):
            if char in visited:
                return visited[char]

            visited[char] = True

            for neighChar in adj[char]:
                if dfs(neighChar):
                    return True

            visited[char] = False
            res.append(char)

        for char in adj:
            if dfs(char):
                return ""

        res.reverse()
        return "".join(res)

Complexity

time: $O(N+V+E)$
space: $O(V + E)$
where V is the number of unique char, E is the number of edges and N is the sum length of all the strings.