九章演算法 | Google 面試題：字典裡面的最長單詞

撰文 | JZ

專欄 | 九章演算法

題目描述

給定一個字元串列表words，找到words最長的word，使得這個word可用words中的其他word一次一個字元地構建。如果有多個可選答案，則返回最長的且具有最小字典序的word。

樣例

Ⅰ. Input: words = ["w","wo","wor","worl", "world"]

Output: "world"

Explanation: 「world」可通過」w」, 「wo」, 「wor」, 「worl」一次一個字元進行構建。

Ⅱ . Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

Output:"apple"

Explanation: 「apply」和」apple」都可以由其他字元構建。但」apple」的字典序要小於」apply」。

注意：

所有的輸入字元只包含小寫字元。

words的長度在[1, 1000]範圍內。

words[i]的長度在[1, 30]範圍內。

解題思路分析

方法一：直接採用暴力搜索。

對於每一個word，檢查是否其前綴都在words中。可以用words構建set。初始化ans=」」，words，對每個元素，在set中尋找是否有其所有前綴。如果當前word合題，且長度大於ans，或長度等於ans但字典序小於ans，則修改ans為當前word。也可以先對words排序，按照長度從小到大，長度相同按照字典順序。這樣只要word合題就修改ans。

時間複雜度：O(sum(w_i^2)),w_i表示words[i]的長度。對於每一個word，通過哈希表檢查是否所有的前綴都在set當中需要O(w_i^2)。

空間複雜度：O(sum(w_i))用於創建set。

方法二：因為涉及到了字元串的前綴，所以使用Trie結構（一種字元串前綴樹）。

先介紹Trie，如果已經了解Trie樹可跳過這部分：

Trie，又稱單詞查找樹或鍵樹，是一種樹形結構。典型應用是用於統計和排序大量的字元串（但不僅限於字元串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：最大限度地減少無謂的字元串比較，查詢效率比哈希表高。

它有3個基本性質：

1.根節點不包含字元，除根節點外每一個節點都只包含一個字元。

2.從根節點到某一節點，路徑上經過的字元連接起來，為該節點對應的字元串。

3.每個節點的所有子節點包含的字元都不相同。

Trie中每個節點有一個特殊標記作為結束符號，通過該標記可以判斷當前節點是否是一個字元串的終結節點。

下圖是一個Trie樹的例子，記錄了to,tea,ted,ten,a,i,in,inn這些words（以藍色結尾）。

把每個word放入Trie中，對Trie進行DFS，只搜索終結節點。每個找到的節點中（除了根）從根到該節點路徑代表該節點的word。之後同方法一：如果當前word合題，且長度大於ans，或長度等於ans但字典序小於ans，則修改ans為當前word。

時間複雜度：O(sum(w_i))，w_i是words[i]的長度。這是構建和便利Trie的複雜度。如果使用BFS而不是DFS，並且把每個節點的子節點進行排序，那麼我們就不需要再去檢查當前的word時候比ans要好，後訪問的節點一定要好於先訪問的節點，但複雜度不變。

空間複雜度：O(sum(w_i))用於構建Trie。

參考程序

http://www.jiuzhang.com/solution/longest-word-in-dictionary/

面試官角度分析

本題是一道中等難度的題目，主要考察了Hash表和Trie這兩種數據結構，可以區分幾類面試者。對於想到Hash表來實現方法一的面試者可以給出hire；對於會用Trie樹實現方法二的面試者給出strong hire。

lintcode相關問題

http://www.lintcode.com/en/problem/longest-words/

http://www.lintcode.com/problem/implement-trie/