目录

牛客_数组中两个字符串的最小距离

解析代码

---

牛客_数组中两个字符串的最小距离

数组中两个字符串的最小距离__牛客网

        给定一个字符串数组strs，再给定两个字符串str1和str2，返回在strs中str1和str2的最小距离，如果str1或str2为null，或不在strs中，返回-1。

---

解析代码

思路：贪心

1.如果暴力：两层for循环枚举，数据范围是10^5，会超时。

2.用贪心（dp）来优化。

3.用若干个变量来标记某个位置前驱的最优解（常用优化方法）预处理思想，只管左边，不管右边。当遍历到后面的时候，向左看，会包含之前右边的情况。

4.prev1：标记的是遍历到i位置时，左边最近符合要求的下标。

5.prev2：标记的是i遍历到了符合要求的另一个下标。

时间复杂度：O（N）

#include <iostream>
#include <unordered_map>
#include <vector>
#include <climits>
using namespace std;
int main()
{string str1, str2;int n = 0; // strs的长度cin >> n >> str1 >> str2;vector<string> strs(n);for (int i = 0; i < n; ++i){cin >> strs[i];}if (str1.empty() || str2.empty()){cout << -1;return 0;}bool flag = false;vector<int> leftPos, rightPos;for (int i = 0; i < n; ++i){if (strs[i] == str1){leftPos.push_back(i);}else if (strs[i] == str2){rightPos.push_back(i);}}if (leftPos.empty() || rightPos.empty()){cout << -1;return 0;}int res = INT_MAX;for (int i = 0; i < leftPos.size(); ++i){for (int j = 0; j < rightPos.size(); ++j){res = min(res, abs(leftPos[i] - rightPos[j]));}}cout << res;return 0;//for (int left = 0, right = 0; right < n; ++right)//{//	string tmp; // 前一次出现的//	if (strs[right] == str1)//	{//		tmp = strs[right];//		begin = right;//	}//	else if (strs[right] == str1 || strs[right] == str2 && begin != -1)//	{//		tmp = strs[right];//		end = right;//	}//	while (tmp == strs[left])//}//return 0;
}