笔试题2 -- 字符串数组中指定字符串间的最短距离

字符串数组中指定字符串间的最短距离

文章目录

字符串数组中指定字符串间的最短距离
- 题目还原
- 解法一：暴力遍历 (HashVector法)
- 解法二：算法改进 (双指针法)
- 总结

题目链接： 数组中两个字符串的最小距离 – 牛客网

题目还原

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

输入描述:

输入包含有多行。第一输入一个整数n (1≤n≤10^5) ，代表数组strs的长度。第二行有两个字符串分别代表 str1 和 str2，接下来n行，每行一个字符串，代表数组strs (保证题目中出现的所有字符串长度均小于等于10)。

输出描述:

输出一行，包含一个整数，代表返回的值。

备注:

时间复杂度O（n），额外空间复杂度O（1）

解法一：暴力遍历 (HashVector法)

思路摘要

通过创建一个哈希向量来标记str1和str2在数组中的位置，然后通过两个嵌套循环来查找最小距离。

// 利用哈希关系对应 str1 和 str2 找到的位置
vector<int> HashVector(const vector<string>& strs, const string& str1, const string& str2)
// 遍历哈希表找到两字符串间的最短距离
int LowerWay(const vector<int>& v)

代码示例：

#include string"><iostream>
#include string"><string>
#include string"><vector>
#include string"><climits>using namespace std;vector<int> HashVector(const vector<string>& strs,const string& str1, const string& str2) {// str1对应位置设为1，str2对应位置设为2// 否则为0int n = strs.size();vector<int> hash_v(n, 0);for (int i = 0; i < n; i++) {if (strs[i] == str1) {hash_v[i] = 1;} else if (strs[i] == str2) {hash_v[i] = 2;}}return hash_v;
}int LowerWay(const vector<int>& v) {int n = v.size();int min = INT_MAX;bool have_s1 = false;bool have_s2 = false;for (auto e : v) {if (e == 1) {have_s1 = true;}if (e == 2) {have_s2 = true;}}if (!have_s1 || !have_s2) {return -1;}for (int i = 0; i < n; i++) {if (v[i] != 1) {continue;}for (int j = n - 1; j > 0; j--) {if (v[j] != 2) {continue;}int length = abs(i - j);min = (min < length) ? min : length;}}for (int i = 0; i < n; i++) {if (v[i] != 2) {continue;}for (int j = n - 1; j > 0; j--) {if (v[j] != 1) {continue;}int length = abs(i - j);min = (min < length) ? min : length;}}return min;
}void test() {// 接收输入int n = 0;cin >> n;string str1;string str2;cin >> str1 >> str2;if (str1.empty() || str2.empty()) {cout << -1 << endl;return;}vector<string> strs(n);for (int i = 0; i < n; i++) {cin >> strs[i];}vector<int> v = HashVector(strs, str1, str2);cout << LowerWay(v) << endl;
}int main() {test();return 0;
}

提交截图：

在这里插入图片描述

评价：

这种方法在处理大数据集时可能会有性能问题，因为它的时间复杂度为O(n^2)。

解法二：算法改进 (双指针法)

思路摘要

在遍历数组时，记录下str1和str2最后出现的位置，并实时更新最小距离。

代码示例：

#include string"><iostream>
#include string"><string>
#include string"><vector>
#include string"><limits>using namespace std;int findMinDistance(const std::vector<std::string>& strs, const std::string& str1, const std::string& str2) {int minDistance = std::numeric_limits<int>::max();int lastPos1 = -1, lastPos2 = -1;for (int i = 0; i < strs.size(); ++i) {if (strs[i] == str1) {lastPos1 = i;// 当str2也已找到时，计算距离if (lastPos2 != -1) {minDistance = std::min(minDistance, abs(lastPos1 - lastPos2));}} else if (strs[i] == str2) {lastPos2 = i;// 当str1也已找到时，计算距离if (lastPos1 != -1) {minDistance = std::min(minDistance, abs(lastPos1 - lastPos2));}}}// 如果str1或str2未在数组中找到，返回-1if (lastPos1 == -1 || lastPos2 == -1) {return -1;}return minDistance;
}int main() {int n;std::cin >> n;std::string str1, str2;std::cin >> str1 >> str2;std::vector<std::string> strs(n);for (int i = 0; i < n; ++i) {std::cin >> strs[i];}int result = findMinDistance(strs, str1, str2);std::cout << result << std::endl;return 0;
}