Facebook高频题 | Shortest Word Distance的多个变种和解法

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”