目录
牛客_数组中两个字符串的最小距离
解析代码
牛客_数组中两个字符串的最小距离
数组中两个字符串的最小距离__牛客网
给定一个字符串数组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;
}
