Shortest Word Distance是Facebook、LinkedIn等公司的高頻面試題。
這個題目本身不是很難，但卻有很多follow up問題。今天我們就針對這個題目進行講解和延伸，幫助大家梳理拓寬思路，更好接招面試官的層層追問。
先一起來看看題目：
題目描述
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
Note：
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Input:word1 = “coding”, word2 = “practice”Output:3
Input:word1 = "makes", word2 = "coding"Output:1
考點解析
shortest word distance是Facebook非常高頻的一道面試題目。
這道題目有很多變種。不同於以往我們把一個題目講的比較細緻，今天這個題目，我們希望將多個變種串起來講，並且再多延伸一些。
希望通過這道習題，幫助大家開闊思路，瞭解這個看似不那麼困難的題目，在面試中會怎樣被面試官步步延伸和追問。這也正是facebook特別喜歡考這道題的原因。
主講人：Emma老師
FLGU一線公司資深工程師
掃描下方二維碼
進入來Offer官網觀看
解題思路
在這道題目中，Emma老師講解了多個不同的解法，以及follow up問題的回答思路。
Solution 1: Naive Solution
拿到題目，一個比較自然的想法就是把array從左到右遍歷一遍，記錄word1和word2所出現的位置，得到兩個sorted index list。
以下面的這個例子來說：
0 1 2 3 4 5 6 7
[a, c, d,b, b, b, c,a]
Input：
word1 = "a"
word2 = "b"
則遍歷後的list分別為：
la: 0, 7
lb: 3, 4, 5
經過這一步的處理，這個題目就變成了從la取一個數字，從lb取一個數字，差值最小的組合是什麼。
最brute force的做法，就是計算出所有可能的組合的差，再從中選擇最小的一對。但顯然，這是一個複雜度比較高的做法，我們可以在這個基礎上進行優化。
Optimize 1: Binary Search
已知這兩個list都是排好序的，那我們就可以利用binary search：
對於a裡面的每一個元素，在b裡面進行binary search，找到離a中元素最近的那個元素。之後再在所有結果中取一個最近的結果。
思考題
對a中的元素在b中進行binary search，和對b中的元素在a中進行binary search時間複雜度有區別嗎？
Optimize 2: Two Pointer
再進一步，兩個list都是sorted，要找到最小距離的情況，我們應該可以想到，這是一個典型的two pointer誰小移誰的問題。
我們可以分別在a、b兩個list放置兩個pointer，每次移動兩個pointer中，對應的元素中相對較小的一個，同時計算一下兩個pointer對應元素相差的距離，在需要更新的時候更新。
也就是說：
if la(i) is smaller, lb(j) is the smallest larger element in lb comparing to la(i)
if lb(j) is smaller, la(i) is the smallest larger element in la comparing to lb(j)
Solution 2
我們是否可以不建這兩個list呢？能否只是從左到右遍歷一遍原array，忽略無關的元素，只去看a和b呢？也是可以的。
我們換一種分解問題的方法，把這個問題考慮為：
For each a, we need to get the most recent position of b.
For each b, we need to get the most recent position of a.
這樣他們中差值最小的那個，就是我們需要的答案。
那麼在實現的時候，我們就需要從左到右掃一遍array，並記錄：
IndexA：最近一次出現a的位置
IndexB：最近一次出現b的位置
Result：當前的最短距離
每當我們找到一個a或者b時，我們就要檢查IndexB和IndexA之間的差是否比result的值小，如果是，則更新result的值，直到遍歷完整個array。
在講解Follow Up問題前，我們先看一下這個解法的代碼實現：
代碼實現
Follow Up 1:
Multiple query with unlimited times
原問題只是query一次，而且是確定的兩個單詞。那麼，如果是要query很多次，而且單詞是不固定的，那麼應該怎樣更好的解決這個問題呢？
在這種情況下，如果使用之前的方法，我們就需要在每次query的時候都把array掃一遍，cost非常大。
我們應該想到這個題目的需要precomputation。
比較直接的一個方法，就是使用一個hashmap，記錄所有distinct word出現的位置。那麼，在query某兩個word的時候，只需要看那兩個word的list就可以了。省去了反覆遍歷原array的時間。
進一步，還可以和麵試官探討，如果某個組合被query了很多次，那我們是否需要cache這個結果。
另外一個要與面試官討論的就是，假設我需要非常快的返回這個結果，而且重複query的情況非常多。那我可能需要
直接將每兩個word的最短距離直接記下來，這樣之後的每次query都只需要O(1)的時間了。思考題：
如果這樣的話，precomputation的效率如何，有沒有什麼tradeoff？是否是所有情況下都合適的方法？
Follow Up 2:
Find the Shortest Word Distance
Among k Words
這個題目的另一種變形方式就是，我不只求2個word的最短距離，而是多個word的最短距離。
這裡距離的定義是在原input array中最小的subarray的長度，這個subarray需要包含所有k個指定的words。
那這時又要如何求解呢？
與上面思路相承接，一個可能的解法是，針對k個字母，都建立一個list。問題轉化為：從這k個list中，各抽一個元素，使得其最大值和最小值的差最小。
這時，我們利用k pointer的方法，使用priority queue，tree set或者tree map等數據結構都可以解決。
另一個思路，是將這道題目與minimum substring window聯繫起來，可以用sliding window的方法來解決。
更多科技求職資訊，請關注”來Offer”
閱讀更多 LaiOffer來Offer 的文章
