269. Alien Dictionary - cocoder39/coco39_LC GitHub Wiki

269. Alien Dictionary

Notes 2022:

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        indegree = {}
        for word in words:
            for ch in word:
                indegree[ch] = 0 # avoid missing letters which don't have order relationship with other letters eg d in abc vs abcd
        
        n = len(words)
        sourToDestList = collections.defaultdict(set)
        for i in range(1, n):
            diff = False
            firstWord, secondWord = words[i-1], words[i]
            length = min(len(firstWord), len(secondWord))
            for j in range(length):
                if firstWord[j] != secondWord[j]:
                    diff = True
                    if secondWord[j] not in sourToDestList[firstWord[j]]: # uniqueness to help update indegree
                        sourToDestList[firstWord[j]].add(secondWord[j])
                        indegree[secondWord[j]] += 1
                    break
            if not diff and len(firstWord) > len(secondWord): # edge invalid case
                return ''
        
        queue = collections.deque()
        for ch, d in indegree.items():
            if d == 0:
                queue.append(ch)
        
        order = []
        while queue:
            cur = queue.popleft()
            order.append(cur)
            for next in sourToDestList[cur]:
                indegree[next] -= 1
                if indegree[next] == 0:
                    queue.append(next)
        if len(order) != len(indegree): # cycle causes some edge cannot be removed
            return ''
        
        return ''.join(order)

step 1 - extract out edges: pitfalls: (1) given ["ab, ac"], we won't miss "b"->"c" but we also need to include "a" as a node in graph (2) "abc" < "ab" => return ""

step 2 - get topological order

Option 1 - use in degree: pay attention to how to detect cycle if len(order) < len(indegrees)

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        indegrees = {}
        for word in words:
            for ch in word:
                indegrees[ch] = 0
        
        rules = collections.defaultdict(set)
        for i in range(1, len(words)):
            rule = []
            for ch1, ch2 in zip(words[i-1], words[i]):
                if ch1 != ch2:
                    rule = [ch1, ch2]
                    if rule[1] not in rules[rule[0]]:
                        rules[rule[0]].add(rule[1])
                        indegrees[rule[1]] += 1
                    break
            if rule == [] and len(words[i-1]) > len(words[i]):
                return ""
        
        queue = collections.deque()
        for key in indegrees.keys():
            if indegrees[key] == 0:
                queue.append(key)
        
        order = []
        while queue:
            cur = queue.popleft()
            order.append(cur)
            for next in rules[cur]:
                indegrees[next] -= 1
                if indegrees[next] == 0:
                    queue.append(next)
        
        if len(order) < len(indegrees):
            return ""
        return "".join(order)

Option 2 - use dfs traversal: Algorithm: visited[node] = 0 : node hasn't been visited visited[node] = 1: node is in current stack visited[node] = 2: node, node's adjacent nodes, adjacent nodes' adjacent nodes have been explored.

cycle detection: meet a node visited[node] = 1, which indicates it is in current stack pitfall: order is reverse of what we need

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj_list = {ch: [] for word in words for ch in word}
        for i in range(1, len(words)):
            all_match = True
            for ch1, ch2 in zip(words[i-1], words[i]):
                if ch1 != ch2:
                    all_match = False
                    if ch2 not in adj_list[ch1]:
                        adj_list[ch1].append(ch2)
                    break
            if all_match and len(words[i-1]) > len(words[i]):
                return ""
            
        visited = {ch: 0 for word in words for ch in word}
        order = []
        for node in adj_list.keys():
            if visited[node] == 0:
                if not self.dfs(adj_list, node, visited, order):
                    return ""
        order.reverse()
        return "".join(order)
    
    def dfs(self, adj_list: map, node: str, visited: map, order: list) -> bool:
        visited[node] = 1
        for next_node in adj_list[node]:
            if visited[next_node] == 1:
                return False
            if visited[next_node] == 0:
                if not self.dfs(adj_list, next_node, visited, order):
                    return False
        visited[node] = 2
        order.append(node)
        return True
⚠️ **GitHub.com Fallback** ⚠️