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

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

题目还原

给定一个字符串数组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 <iostream>
#include <string>
#include <vector>
#include <climits>

using namespace std;

vector<int> HashVector(const vector<string>& strs,
                       const string& str1, const string& str2) {
    // str1对应位置设为1，str2对应位置设为2
    // 否则为0
    int 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 <iostream>
#include <string>
#include <vector>
#include <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未在数组中找到，返回-1
    if (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;
}

提交截图：

评价：

这种方法的时间复杂度为O(n)，在处理大数据集时更加高效。

总结

​ 本文中我们探讨了两种不同的C++解题方法。从基本的暴力法到更高效的优化算法，我们不仅学习了如何实现它们，还了解了如何分析它们的性能，并在实际应用中做出合适的选择。