题目来源：牛客
[编程题] 数组中两个字符串的最小距离
题目描述：
给定一个字符串数组 strs ，再给定两个字符串 str1 ， str2 ，返回在 strs 中 str1 和 str2 的最小距离，如果 str1 或 str2 为 null ，或不在 strs 中，返回 -1 。
输入描述：
输入包含有多行，第一行输入一个整数 n （1 ≤ n ≤ 105） ，代表数组 strs 的长度，第二行有两个字符串分别代表 str1 和 str2 ，接下来 n 行，每一行一个字符串，代表数组 strs （保证题目中出现的所有字符串长度均小于等于 10 ）。
输出描述：
输出一行，包含一个整数，代表返回的值。
示例1
输入：1
CD AB
CD
输出：-1
说明：strs 数组为[“CD”]，由于"AB"不在 strs 里，返回 -1
示例2
输入：5
QWER 666
QWER
1234
qwe
666
QWER
输出：1
说明：strs 数组为[“QWER”，“1234”，“qwe”，“666”，“QWER”]，其中"QWER"和"666"的最短距离为 1（选择第四个和第五个字符）
解析
这题有两个解法：①暴力枚举，两成循环遍历，找出每个 str1 和 str2 之间的距离，求出最小值。但由于这一题数据量是 105 级别，两次循环肯定是要超时的，所以这里就不实现了。②贪心，我们使用贪心只需要一层遍历就可以找出最小值。我们遍历到 str1 或 str2 时，用变量存这个位置之前，并且最近的 str2 或 str1 的下标，相减就是当前的距离，直到遍历完，找出最小距离。
代码实现
#include<iostream> #include<string> using namespace std; int main() { int n; string str1, str2; string strs; cin >> n; cin >> str1 >> str2; // 记录 str1 的下标 int prev1 = -1; // 记录 str2 的下标 int prev2 = -1; // 记录答案，初始为答案不可能达到的最大值 int ans = 1e5 + 10; // 每次遍历与后面的数据无关，所以可以读一个判断一下 for (int i = 0; i < n; ++i) { cin >> strs; // 如果遍历到的值为 str1 ，则去前面找最近的 str2 if (strs == str1) { // 前面出先过 str2 if (prev2 != -1) { // 找到小值 ans = min(ans, i - prev2); } // 更新 str1 的下标 prev1 = i; } else if (strs == str2) { if (prev1 != -1) { ans = min(ans, i - prev1); } prev2 = i; } } // 根本没有更新答案，说明没有结果 if (ans == 1e5 + 10) { cout << -1; } cout << ans; return 0; }
