Leetcode 269: Alien Dictionary

Total Accepted: 1390 Total Submissions: 8315 Difficulty: Hard

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note:

  1. You may assume all letters are in lowercase.
  2. If the order is invalid, return an empty string.
  3. There may be multiple valid order of letters, return any one of them is fine.

Code

from sets import Set

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        if not words:
            return ""

        if len(words) == 1:
            return "".join([s for s in Set(words[0])])

        # len(words) >=2
        adj_dict = self.build_graph(words)
        visit_dict = dict([(k,0) for k in adj_dict.keys()])
        res = []
        self.valid = True
        
        for c in adj_dict.keys():
            self.topo_sort(c, visit_dict, adj_dict, res)
        return "".join([s for s in res]) if self.valid else ""

    def build_graph(self, words):
        adj_dict = {}

        def add_node(c):
            if adj_dict.get(c, None) == None:
                adj_dict = {}

        def add_link(src, des):
            adj_dict[src][des] = None

        for i in xrange(len(words)-1):
            w1 = words[i]
            w2 = words[i+1]
            start2 = 0
            for j in xrange(min(len(w1), len(w2))):
                if w1[j] == w2[j]:
                    add_node(w1[j])
                else:
                    add_node(w1[j])
                    add_node(w2[j])
                    add_link(w2[j], w1[j]) 
                    start2 = j+1
                    break   
            for j in xrange(start2, len(w1)):
                add_node(w1[j])             
            for j in xrange(start2, len(w2)):
                add_node(w2[j])
                
        return adj_dict

    def topo_sort(self, c, visit_dict, adj_dict, res):
        if self.valid and not visit_dict:
            visit_dict = 1
            for adj_c in adj_dict.keys():
                if visit_dict[adj_c] == 1:
                    self.valid = False
                    return
                if not visit_dict[adj_c] and self.valid:
                    self.topo_sort(adj_c, visit_dict, adj_dict, res)
            
            visit_dict = 2
            res.append(c)
        
                

 

Idea

Build a graph first, in which nodes are letters and a link from letter A to letter B means A should be latter than B in the final order. Then use topological sort to output nodes in order. https://en.wikipedia.org/wiki/Topological_sorting

 

Leave a comment

Your email address will not be published. Required fields are marked *