269. Alien Dictionary

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

Example 1:
Given the following words in dictionary,

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

The correct order is:"wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is:"zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return"".

Note:

1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

Solution：

Time Complexity: O(nk + V + E) where n is number of words, k is average word length, V is number of unique letters, E is number of edges, i.e the relationship of each letter to the other.

The logic is to create the adjacency list first, then do topological sort on the list to find out the letter ordering.

To create adjacency list:

1. create a key in adjacency hashmap for every letter, empty set as value
2. add the ordering of first letter into the hashmap
3. add non-first letter lexicographical ordering into the adjacency hashmap

Now we finish the adjacency list, we can do topological sort to find out the letter precedence relationship.

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

        ####### the hard part is to recognize this problem as a topological sort problem #######
        ## idea: construct the adjacent list order map, then use topological sort for this problem
        # where key or vertex is each letter, edge is the precedence relationship among them

        # if there is a cycle in this graph, aka, order is messed up among the words, return ""

        if words == None or words == []:
            return ""
        n = len(words)
        orders = {}

        # create a key in adjacency hashmap for every letter
        for letter in list("".join(words)):
            if letter not in orders:
                orders[letter] = set()

        # add first letter order into orders. 
        firstLetters = map(lambda word: word[0], words)
        for i in range(len(firstLetters)):
            orders[firstLetters[i]].update(firstLetters[i+1:])

        # add non-first letter lexi orders into orders
        for i in range(n-1):
            l = 0
            while l < min(len(words[i]), len(words[i+1])) and words[i][l] == words[i+1][l]:
                l += 1
            if l < min(len(words[i]), len(words[i+1])):
                orders[words[i][l]].add(words[i+1][l])

        # parameters to pass, orders dictionary, current processing letter, ancestor stack, returnResult, set of visited list
        visited = set()
        orderReturn = []
        print orders
        for letter in orders:
            if letter not in visited:
                res = self.dfsVisit(orders, letter, [], orderReturn, visited)
                orderReturn.append(letter)
                visited.add(letter)
                if res == False:
                    return ""
        return "".join(orderReturn[::-1])

    def dfsVisit(self, orders, letter, ancestors, orderReturn, visited):

        for postLetter in orders[letter]:
            if postLetter == letter:
                continue
            if postLetter in ancestors:
                return False
            if postLetter not in visited:
                res = self.dfsVisit(orders, postLetter, ancestors + [letter], orderReturn, visited)
                visited.add(postLetter)
                if res == False:
                    return False
                orderReturn.append(postLetter)
        return True