九章演算法 | Google 面經：找出dictionary里含某車牌號碼的所有英文字母的最短單詞

撰文 | JZ

專欄 | 九章演算法

學員提問：

給一個車牌號碼(美國的)，以及一個dictionary，請找出dictionary里含有所有該車牌號碼的所有英文字母(case insensitive)的最短字串

ex:

車牌 RO 1287 ["rolling", "real", "WhaT", "rOad"] => "rOad"

follow up:

(1) 如果dictionary里有上百萬個字，該如何加速

(2) 如果dictionary有上百萬個字，然後給你上千個車牌號碼，要你回傳相對應的最短字串，該如何optimize?

若有N個字，車牌長度為M，求問N+M演算法。

請問老師，原貼的討論裡面有提到將每個字母map到一個質數，一個單詞就是所有字母表示質數的乘積。字典里的單詞如果能被輸入的欄位除盡就是含有該輸入字串的單詞，然後求最短就好了。但是感覺這樣還是需要每一個單詞都要掃一遍字典，複雜度並沒有降低。

令狐老師解答

有的同學認為，這道題可以用 trie 解決，但其實用 trie 並不能解決。

因為這個題說的是包含單詞里的所有字母就好了，並沒有要求順序。也就是說從例子中來看，「orad」 也是包含 "RO" 的。

首先這類問題，給一個dictionary的，都是需要對 dictionary 做一些預處理的，因為dictionary又不會隨時變化。既然是google的題，那麼這個題多半就跟倒排索引有關係。一個直觀的解決辦法就是建立倒排索引。

比如 "Access" 這個單詞，出現了 a, c, e, s 四個字母。所以把Access 分別放入 a, c, e, s 的隊列中。

然後假如你來了一個車牌，包含字母ace，如何找到 Access呢？方法是，把 a 的倒排拿出來，c的拿出來，e的拿出來。然後做一次歸併。把同時出現在這三個字母里的倒排里的單詞找到。為了加速演算法，倒排在建立的時候，就可以先按照長度排序，然後相同長度的按照字母序排序。這樣在歸併的時候找到的第一個在三個字母的倒排隊列中出現的單詞，就是答案。

你可能會意識到，這種方法在某些情況下還是很慢，因為比如上百萬個單詞，一共只有26個不同的字母，那麼平均下來，每個字母也有 1m/26 個單詞包含它。歸併的時候效率並不高。那麼怎麼解決呢？上面的演算法的key只有一個字母，自然這個1m/26的分母比較小。我們要想辦法把這個分母變大。答案是，可以用2個字母作為key。

以 Access 為例，出現的字母有 aces，那麼把 ac, ae, as, ce, cs, es 作為倒排的key，把Access 放到這6個key的倒排列表中。當我們需要查詢 ace 被哪些單詞包含的時候，我們就可以歸併 ac 和 e 的倒排表。這就比 並 a, c, e 的三個倒排表要快了。

再進一步，你可以用3個字母作為 key, access => {ace, acs, ces, aes}，這樣一口氣就能找到 ace 了，無需歸併。

進一步分析，你會發現這是一個 tradeoff，就是並不是用越多的字母作為key就越好。假如單詞的平均長度是 L，那麼C(L,1)是有多少個1元的key，C(L,2)是有多少個2元的key（基本是L^2的級別 ），C(L,3)是有多少個3元的key。。。

所以字母越多，一個單詞被重複扔到各個倒排列表中的機會就越多。需要的存儲空間也就越大。介於車牌的字母不是很多，我覺得差不多到3元的key就差不多可以了。