题解 | 数组中两个字符串的最小距离

#include<iostream>
#include<string>

using namespace std;

int main()
{
    int n;
    cin>>n;
    string str1,str2;
    cin>>str1>>str2;
    string s;
    //贪心，假设当前是最小的
    int prev1 =-1,prev2 = -1;
    int ret = 1e9;
    for(int i=0; i < n;i++)
    {
        cin>>s;
        //寻找是否和str1/str2相同的保存位置prev1/prev2
        if(s == str1)
        {
            prev1 = i;
            //从左看是否有str2,更新ret
            if(prev2 != -1)
            {
                ret =min(ret,prev1-prev2);
            }
        }
        if(s == str2)
        {
            prev2 = i;
            if(prev1 != -1) 
            {
                ret = min(ret,prev2 -prev1);
            }
        }
    }
    cout<<((prev1==-1 || prev2==-1) ? -1 : ret)<<endl;
    return 0;
}

这道题我一开始用的是滑动窗口+整体思想，先寻找到str1/str2节点然后保存，然后更新最小值就可以了（细节必须是要都存在数据才能更新）

#include <iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
int n;
cin>>n;
string str1;
string str2;
cin>>str1>>str2;
vector<string> vs(n);
for(int i=0; i < n;i++)cin>>vs[i];
//整体思想+滑动窗口
int left = -1,right = -1;
int ret = 1e9;
for(int i = 0; i < n;i++)
{
if(vs[i] == str1) left = i;
else if(vs[i] == str2) right = i;
//更新结果
if(left != -1 && right != -1)
ret = min(ret,abs(right - left));
}
if(left == -1 || right == -1) cout<<-1<<endl;
else cout<<ret<<endl;
}

我后面发现了一个更加优秀的解法，就是利用贪心，只看局部情况，寻找到一个str1/str2后判断对应位置前面相对的prev2/prev1（prev1对应是str1寻找后的位置，prev2对应的是str2寻找后的位置）然后根据前面是否有对应位置的下标来更新，如果有就更新结果（当然在此之前要先更新对应str1/str2的位置，在更新结果）。解释变量：str1、str2是输入的，prev1对应str1的位置下标要及时更新，prev2对应str2的位置下标

ps：我在写代码的时候发现我更新位置不对（更新位置应该要在prev1/prev2存在的情况下才更新），然后还有一个问题就是更新prev1和prev2时机和理解，prev1是对应str1位置下标（当前最靠str2位置的下标，也就是贪心的核心），同理prev2也是如此