面试题 17.11. 单词距离

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

在一个数组中，找到 $word1$ 和 的最近距离。

题目中的说的「最短距离(相隔单词数)」是错的，应该说是下标之差。

可以根据下图理解题意：

解题方法

分析

做本题需要看一下数据规模，，数据规模很大，如果采用 的算法就会超时。

其实这个数据规模已经在提示我们，使用 或者 的算法。

的算法我就想到双指针。

可以使用两个指针 和 ，一个指向单词 $A$，一个指向单词 $B$，再两个指针移动的过程中一直求两者的最短距离就行了。

为什么这种方法可行呢？

我们假设在数组中靠前的指针是 指向，靠后的指针是 指向 。

无论当前遇到 还是 只用关心其左侧最后一个对方出现的位置。

假设之前的排列方式是「AB」，当遇到新的 或者 时，分两种情况讨论：

1. 当前遇到 $A$

只需要知道最后一个 的位置，求新距离。

1. 当前遇到 $B$

只需要知道最后一个 的位置，求新距离。

你可能会问，为什么只向左侧找最后一个对方，不用向右侧找呢？

因为对于 来说，向右找 ，与 对于右边的 来说，向左找 是等价的。把向右寻找对方的机会，留给对方向左来找你吧。

总之，对于每个 或者 都只用考虑向左找就行了。

代码

如上所述，代码不难吧。记得要对 求绝对值哦！

class Solution {
public:
    int findClosest(vector<string>& words, string word1, string word2) {
        int p1 = -1;
        int p2 = -1;
        const int N = words.size();
        int res = INT_MAX;
        for (int i = 0; i < N; ++i) {
            if (words[i] == word1) {
                p1 = i;
            } else if (words[i] == word2) {
                p2 = i;
            }
            if (p1 > 0 && p2 > 0)
                res = min(res, abs(p1 - p2));
        }
        return res;
    }
};

复杂度

• 时间复杂度：，是单词的个数。
• 空间复杂度：。

总结

1. 问题的简化与抽象，理清这个思路啊！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。