（算法）两个单词的最短距离

AndyJee 2021-11-16 原文

题目：

有个内含单词的超大文本，给定任意两个单词，找出这个文件中两个单词的最短距离。

思路：

通过两个两个变量来记录两个单词最后出现的位置，然后每次计算两者的距离，并更新最小距离。

假设需要重复查找任意两个单词的最短距离，则需要构造一个散列表，记录每个单词及其出现的位置。当查找某两个单词的最短距离时，只需找出该两单词所在列表差值最小的位置。

查找方法：可以将两个有序列表合并（列表元素包含位置及其所属单词，可以构造结构体）。

代码：

#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

int shortest_1(const vector<string> &words,string word1,string word2){
    int min=INT_MIN;
    int len=words.size();
    int lastWord1=-1;
    int lastWord2=-1;
    int distance;

    for(int i=0;i<len;i++){
        string curWord=words[i];
        if(curWord==word1){
            lastWord1=i;
            distance=lastWord1-lastWord2;
            if(lastWord2>=0 && min>distance)
                min=distance;
        }
        else if(curWord==word2){
            lastWord2=i;
            distance=lastWord2-lastWord1;
            if(lastWord1>=0 && min>distance)
                min=distance;
        }
    }
    return min;
}

int main(){
    return 0;
}