Python Solution with Detailed Explanation


  • 0
    G

    Solution

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

    Topological Sort Based Solution

    Synoposis

    • The basic idea behind this problem is simple. Build a graph from the dictionary of words. Then do a topological sort of the words. The meat is in the details and corner cases.

    Meaning of Lexicographically Smaller

    Building an Input Graph

    • Graph is a dictionary with key as character and edge end points as a set
    • Every adjacent pair of word is extracted. All their characters are added to a graph as keys
    • Now every adjacent character is compared. The first non-matching character determines a relationship u -> v and is added to graph. We break at this point since the remainder mis-matches do not imply any relationship.
    • Notice a pair like ("wrtkj","wrt") - > this indicates no relationship since wrt match and then the smaller word is actually longer length than bigger word. This needs to be reported as an error.
    • build_graph method returns the graph. If an error is found, empty graph is returned.

    Topological Sort

    • DFS or BFS can be used to implement topological sort. We use DFS.
    • We run topological sort on each vertex.
    • Topological sort requires a directed acyclic graph. If there is a cycle, we return True.
    • How do we detect a cycle? We use the concept of back-edges. We maintain a visiting and visited array.
    • Topological sort can be implemented using BFS as well. https://www.youtube.com/watch?v=71eHuQvSwc0

    Interesting Examples

    • ["wrtkj","wrt"] # Incorrect input
    • ["a","b","a"] # Cycle
    • ["wnlb"]
    class Solution(object):
        def add_vertices(self, w, graph):
            for ch in w:
                if ch not in graph:
                    graph[ch] = set([])        
            return
        
        def add_words_to_graph(self, graph, w1, w2):
            self.add_vertices(w1, graph)
            self.add_vertices(w2, graph)        
            min_length = min(len(w1), len(w2))
            found = False
            for i in range(min_length):
                if w1[i] != w2[i]:
                    graph[w1[i]].add(w2[i])
                    found = True
                    break
            if found == False and len(w1) > len(w2):
                return False # "abstract", "abs" is an error. But "abs", "abstract" is perfectly fine.
            return True
    
        def build_graph(self, words):
            graph = {}
            for i in range(len(words)-1):
                w1, w2 = words[i], words[i+1]
                if not self.add_words_to_graph(graph, w1, w2):
                    return {}
            self.add_vertices(words[-1], graph)
            return graph
    
        def topo_dfs(self, x, g, visited, visiting, st): # Return True if there is a cycle
            visited.add(x)
            visiting.add(x)
            for nbr in g[x]:
                if nbr in visiting: # Back-Edge!
                    return True
                if nbr not in visited:
                    if self.topo_dfs(nbr, g, visited, visiting, st):
                        return True
            visiting.remove(x)
            st.append(x)
            return False
    
        def alienOrder(self, words):
            """
            :type words: List[str]
            :rtype: str
            """
            if words == []:
                return ""
            graph = self.build_graph(words)
            visited, visiting, st = set([]), set([]), []
            for k in graph.keys():
                if k not in visited:
                    if self.topo_dfs(k, graph, visited, visiting, st):
                        return ""
            st.reverse()
            return "".join(st)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.