九章演算法 | Google、Airbnb、Facebook面試題 : 外星人的字典(Alien Dictionary)

撰文 | JZ

專欄 | 九章演算法

題目描述

外星人有自己的語言。雖然他們使用的字母表和英文相同，但是字母的順序不同。現在你獲得了一部外星人的字典，字典中單詞的順序按照外星人的字母表順序排列。你通過字典分析出外星人的字母順序嗎？

Example：

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

正確順序是」wertf」。

2.如果沒有合法的順序序列，輸出空串

解題思路

本題其實是字典序排序的逆過程：通過排好序的序列推得字母的字典序。從樣例分析，」wrt」小於」wrf」當且僅當t的字典序小於f。也就是說，words[i]小於words[i+1]當且僅當這兩個words第一個不同的字母（設為p和q）p的字典序小於q（或者words[i]是words[i+1]的前綴）。而且我們發現，因為大小關係是有傳遞性的，所以只需比較相鄰的words就可以了。

經過上述分析和處理，我們可以得到若干對字母間的大小關係，期望得到一個完整的字母順序序列。

本題中有一個小技巧，字母抽象為圖中的點，字母間的大小關係(u<v)抽象成圖中的邊(u,v)。然後我們要解決的問題原本是一個找好符合條件的字母排序順序，現在可以轉換為找有向圖是否有拓撲排序。 拓撲排序（ Topological Sort）是解決這類問題最方面、快捷的演算法。

那麼拓撲排序是什麼呢？拓撲排序是把一個有向圖的頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前（若圖中有環則無法得到完整的序列）。

拓撲排序可以在O(m)時間內用寬度優先搜索實現，m為邊數。具體做法為：計算每個頂點的入度，將入度為0的點加入隊列，並把該點從圖中刪去（同時減少從該點出發到其他點的入度），若因此導致其他點入度為0，將那些入度變為0的點也加入隊列；直到隊列無法加入更多點。此時，若全部點都在隊列中，拓撲排序成功，該隊列順序即為字母順序。否則沒有合法的字母順序序列，輸出空串。演算法整體時間複雜度為O(n*length)，n為單詞個數，length為單詞平均長度。

參考代碼

面試官角度分析

本題的難點是在首先怎麼想到要把題目轉化為一堆字母的大小關係，然後第二步難點是怎麼把字母的大小關係轉換為有向圖，第三步考察難點是怎麼想到把有向圖的問題用拓撲排序解決。 如果能夠做出來，最後可以達到hire。

LintCode相關練習

http://www.lintcode.com/en/problem/topological-sorting/