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 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".

解题方法

因为word是按照alien dictionary的顺序sort过的，所以我们可以根据相邻的word 知道一些character之间的前后关系。 比如"wrt"在"wrf"之前，那么"t"肯定在"f"之前。

所以首先我们要建立这一关系，两两word比较，第一不同的character就可以建立 前后关系了。我们可以将这一关系存在一个hashmap里。

如果两个character之间有cycle，那么这个就不能成立，所以我们要有detect cycle 的过程。注意，有cycle应该是指当前这个dfs中会回到自身，在之后的dfs中再次 visit这个node不算cycle, 但是应该标记它已经visit过了直接return。所以visit应该有 3个状态

• 未visit: 0
• 当前dfs的起点: 1
• 已经dfs过所以child,之前可以visit: 2

Solution

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        self.c_map = {c: [] for word in words for c in word}
        for word1, word2 in zip(words[:-1], words[1:]):
            for i in range(min(len(word1), len(word2))):
                if word1[i] != word2[i]:
                    self.c_map[word1[i]].append(word2[i])
                    break
        self.visited = {}
        self.circle = False
        stack = []
        for k in self.c_map:
            if self.circle:
                break
            if k not in self.visited:
                self.dfs(k, stack)

        if self.circle:
            return ""
        stack = stack[::-1]
        return "".join(stack)

    def dfs(self, k, stack):
        if self.circle:
            return
        if k in self.visited:
            if self.visited[k] == 1:
                self.circle = True
            return
        self.visited[k] = 1 # start current dfs, shouldn't come back
        for nb in self.c_map[k]:
            self.dfs(nb, stack)
        stack.append(k)
        self.visited[k] = 2 # this traversal is done, can come back from other nodes

Reference