题目
原文：
You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution?
译文：
有一个很大的文本文件，里面包含许多英文单词。给出两个单词，找到它们的最短距离 (以它们之间隔了多少个单词计数)。你能在O(1)的时间内返回任意两个单词间的最短距离吗？ 你的解法空间复杂度是多少？
解答
先看一个例子，为了简单起见，我们假设文件里就只有以下两句话。然后， 我们现在来求is和name的最短距离。假设相邻的两个单词距离为1。
1
What is your name My name is Hawstein
首先，我们遇到的第一个问题是：是否要考虑顺序？我们求的是is和name间的距离， 那么文本中先出现name再出现is的情况要不要算进来。这一点是要和面试官进行交流确认的。 这里我们假设不考虑顺序，并且认为本文中只有单词，没有标点。 为了进一步简化问题，我们可以用一个字符串数组来保存单词， 接下来考虑如何计算两个单词间的最短距离。
最直观的一个解法是，遍历单词数组，遇到is或name就更新它们的位置， 然后计算is和name之间的距离，如果这个距离小于之前的最小距离，则更新这个最小距离。 看图示：
1
2
3
What is your name My name is Hawstein
0 1 2 3 4 5 6 7
p
p表示遍历的当前位置。此时已经经过了前面的一个is和name，is位置为1，name位置为3， 最小距离min=3-1=2。当p移动到下一个单词，发现是name，则更新name的位置为5， 减去is的位置1得到4，并不小于min，不更新，继续。当p移动到is，更新is的位置为6， 减去name的位置5，得到距离为1，小于min，更新min=1。p之后一直移动到末尾， 没遇到is或name，不再更新。最后返回最小值min。时间复杂度O(n)，空间复杂度O(1)。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int ShortestDist(string text[], int n, string word1, string word2){
int min = kMaxInt / 2;
int pos1 = -min;
int pos2 = -min;
for(int pos=0; pos<n; ++pos){
if(text[pos] == word1){
pos1 = pos;
int dist = pos1 - pos2;
if(dist < min)
min = dist;
}
else if(text[pos] == word2){
pos2 = pos;
int dist = pos2 - pos1;
if(dist < min)
min = dist;
}
}
return min;
}
题目要求在O(1)的时间内返回两个单词的最短距离，上述代码肯定是无法满足要求的。 那要怎么做呢？只能用哈希表做预处理了，空间换时间。
方法一
遍历一次文本，用哈希函数将每个单词映射到不同结点，结点后保存该单词出现的位置。 比如对于上面的例子
1
2
What is your name My name is Hawstein
0 1 2 3 4 5 6 7
遍历一次并处理后，我们得到每个单词在文本中出现的位置：(哈希值是随便写的，示意用)
1
2
3
4
5
6
7
单词 哈希值 出现位置
What: 3 0
is: 7 1, 6
your: 13 2
name: 14 3, 5
My: 25 4
Hawstein: 27 7
求两个单词间的最小距离时，首先用O(1)时间通过哈希函数映射到指定结点， 然后对于其中一个单词的每个位置，去与第二个单词的所有位置比较，找到最小的差值。 由于位置是递增的，因此可以修改二分查找进行搜索。
该方法的平均查找复杂度应该是O(1)的，但最坏情况下无法保证O(1)的查找时间， 考虑一种极端情况，文本中的单词就只有is和name，它们的数量各为(1/2)n， 使用这种算法，我们需要O(nlogn)的时间。
方法二
预处理阶段把文本中任意两个单词间的最小距离计算出来， key是两个单词连接后的哈希值，value保存的就是最小距离。 查找阶段就只需要把两个单词连接求其哈希值，然后直接返回其对应的value即可。 查找两个单词的最小距离时间复杂度O(1)。需要O(n^2 )的时间来做预处理。
由于我们是不考虑顺序的，因此做两个单词的连接时，不能直接连接， 这样会导致is和name连接后是isname，而name和is连接后nameis， 它们的哈希值不一样，这并不是我们想要的。因此，在做两个单词的连接时， 我们可以让第一个字符较小的单词放在前面(反正定义一个规则来保证连接的唯一性即可)。 比如对于name和is，由于在字典序中，i<n，所以连接是isname。
还是用上面的例子，预处理后得到：(哈希值是随便写的数字，示意用)
1
2
3
4
5
6
7
单词连接 哈希值 最小距离
(isWhat) 8 1
... ... ...
(isname) 12 1
... ... ...
(isMy) 33 2
... ... ...
这样当我要求is和name之间的最小距离时，就只需要先连接它们得到isname， 然后用哈希函数求出isname的哈希值12，然后直接返回它对应的最小距离即可。
如果有冲突怎么办？即两个不同的字符串映射到同一个哈希值，我们可以用链地址法， 把冲突的连接字符串链接起来，这样每个结点就需要保存连接字符及其对应的最小距离。 比如对于上面的例子，假设isname和isMy的哈希值相同，我们可以按如下所示去做：
1
2
3
4
5
哈希值 最小距离
8 (isWhat,1)
... ...
12 (isname,1) -> (isMy,2)
... ...
这样一来，当我们求得一个连接字符串str的哈希值是12， 就依次去与其后面的结点做比较。如果str等于isname，返回1；否则，移动到下一个结点， 继续比较。如果str等于isMy，返回2。
方法三
也可以先将两个单词分别映射到两个哈希值，比如is映射到哈希值i，name映射到哈希值j， 然后将它们的最小距离保存在d[i][j]中。这里由于是不考虑单词顺序的，因此， 我们可以将较小的哈希值放在d的第一维，较大的放在第二维。也就是对于d[i][j]， 有i<j。同样，这种方法也要考虑冲突问题。
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/03/02/20.5/
