给出两个单词，找到它们的最短距离
题目
有一个很大的文本文件，里面包含许多英文单词。给出两个单词，找到它们的最短距离 (以它们之间隔了多少个单词计数)。你能在O(1)的时间内返回任意两个单词间的最短距离吗？ 你的解法空间复杂度是多少？
解答
先看一个例子，为了简单起见，我们假设文件里就只有以下两句话。然后， 我们现在来求is和name的最短距离。假设相邻的两个单词距离为1。
| 1 2 | What is your name My name is Hawstein |
首先，我们遇到的第一个问题是：是否要考虑顺序？我们求的是is和name间的距离， 那么文本中先出现name再出现is的情况要不要算进来。这一点是要和面试官进行交流确认的。 这里我们假设不考虑顺序，并且认为本文中只有单词，没有标点。 为了进一步简化问题，我们可以用一个字符串数组来保存单词， 接下来考虑如何计算两个单词间的最短距离。
最直观的一个解法是，遍历单词数组，遇到is或name就更新它们的位置， 然后计算is和name之间的距离，如果这个距离小于之前的最小距离，则更新这个最小距离。 看图示：
| 1 2 3 4 | 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 3 | What is your name My name is Hawstein 0 1 2 3 4 5 6 7 |
遍历一次并处理后，我们得到每个单词在文本中出现的位置：(哈希值是随便写的，示意用)
| 1 2 3 4 5 6 7 8 | 单词 哈希值 出现位置 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，它们的数量各为(½)n， 使用这种算法，我们需要O(nlogn)的时间。
方法二
预处理阶段把文本中任意两个单词间的最小距离计算出来， key是两个单词连接后的哈希值，value保存的就是最小距离。 查找阶段就只需要把两个单词连接求其哈希值，然后直接返回其对应的value即可。 查找两个单词的最小距离时间复杂度O(1)。需要O(n2 )的时间来做预处理。
由于我们是不考虑顺序的，因此做两个单词的连接时，不能直接连接， 这样会导致is和name连接后是isname，而name和is连接后nameis， 它们的哈希值不一样，这并不是我们想要的。因此，在做两个单词的连接时， 我们可以让第一个字符较小的单词放在前面(反正定义一个规则来保证连接的唯一性即可)。 比如对于name和is，由于在字典序中，i 还是用上面的例子，预处理后得到：(哈希值是随便写的数字，示意用) 这样当我要求is和name之间的最小距离时，就只需要先连接它们得到isname， 然后用哈希函数求出isname的哈希值12，然后直接返回它对应的最小距离即可。 如果有冲突怎么办？即两个不同的字符串映射到同一个哈希值，我们可以用链地址法， 把冲突的连接字符串链接起来，这样每个结点就需要保存连接字符及其对应的最小距离。 比如对于上面的例子，假设isname和isMy的哈希值相同，我们可以按如下所示去做： 这样一来，当我们求得一个连接字符串str的哈希值是12， 就依次去与其后面的结点做比较。如果str等于isname，返回1；否则，移动到下一个结点， 继续比较。如果str等于isMy，返回2。 方法三 也可以先将两个单词分别映射到两个哈希值，比如is映射到哈希值i，name映射到哈希值j， 然后将它们的最小距离保存在d[i][j]中。这里由于是不考虑单词顺序的，因此， 我们可以将较小的哈希值放在d的第一维，较大的放在第二维。也就是对于d[i][j]， 有i 1 2 3 4 5 6 7 8 单词连接 哈希值 最小距离 ( isWhat ) 8 1 . . . . . . . . . ( isname ) 12 1 . . . . . . . . . ( isMy ) 33 2 . . . . . . . . . 1 2 3 4 5 6 哈希值 最小距离 8 ( isWhat , 1 ) . . . . . . 12 ( isname , 1 ) -> ( isMy , 2 ) . . . . . . 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
