269.Alien Dictionary

Tags: [topological_sort], [DFS], [lexicographical]

Com: {fb}

Link: https://leetcode.com/problems/alien-dictionary/#/description

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 non-empty words from the dictionary, where words 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: Topological Sort

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

        graph = {}
        for w in words:
            for c in w:
                if c not in graph:
                    graph[c] = set()

        for i in xrange(len(words) - 1):
            w1 = words[i]
            w2 = words[i + 1]
            for j in xrange(min(len(w1), len(w2))):
                if w1[j] != w2[j]:
                    graph[w2[j]].add(w1[j])
                    break

        result = self.topological_sort(graph)
        return ''.join(result)

    def topological_sort(self, graph):
        if not graph:
            return []

        result = []
        permanent_visited = set()
        tmp_visited = set()
        for v in graph:
            if v in permanent_visited:
                continue
            try:
                self.dfs(graph, v, result, permanent_visited, tmp_visited)
            except ValueError, e:
                return []

        return result

    def dfs(self, graph, v, result, permanent_visited, tmp_visited):
        tmp_visited.add(v)

        for child in graph[v]:
            if child in permanent_visited:
                continue
            if child in tmp_visited:
                raise ValueError('the input in invalid')

            self.dfs(graph, child, result, permanent_visited, tmp_visited)

        tmp_visited.remove(v)
        permanent_visited.add(v)
        result.append(v)

Revelation:

• Be attention to how do we draw the dependencies graph: First using all chars to initialize the graph, this is necessary, because there exists the case such as: words = ['wrf', 'wrfc']. Then each time compare two row words, scan these two words char by char until find the different char, once find the different char, stop.

Note:

• Time complexity = O(num of all chars).