博文中会简要介绍Leetcode P0243题目分析及解题思路。

“Shortest Word Distance”是一道很简单的题目，主要思路是运用双指针的思想。

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example: Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1

Note:

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

这道题如果使用类似哈希表存储位置信息，再逐一比较得到最小距离的方法，时间复杂度变成O(n^2)。但实际上，如果我们利用双指针，就可以得到线性时间复杂度的解法。

如果我们分别用p1和p2来记录最新的word1和word2的位置，直觉上来讲，当我们遍历到一个和word1相同的单词时，当前最短距离显然是这个单词的位置和p2的差与之前得到的距离中的较小值，反之对于word2也同理。换言之，我们并不关心离这个单词更远的p2（word2的位置），只关心最新的p2。自然地，我们就可以通过使用双指针来记录和更新。

以下是Java的题解代码实现。

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int p1 = -1, p2 = -1, N = words.length, minDist = N;
        for (int idx=0; idx<N; ++idx) {
            if (words[idx].equals(word1)) {
                p1 = idx;
                if (p2 != -1)
                    minDist = Math.min(minDist, Math.abs(p1-p2));
            }
            else if (words[idx].equals(word2)) {
                p2 = idx;
                if (p1 != -1)
                    minDist = Math.min(minDist, Math.abs(p1-p2));
            }
        }
        
        return minDist;
    }
    
}

以下是C++的题解代码实现。

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int p1 = -1, p2 = -1, N = words.size(), min_dist = N;
        for (int idx=0; idx<N; ++idx) {
            if (words[idx] == word1) {
                p1 = idx;
                min_dist = (p2 != -1)? min(min_dist, abs(p1-p2)): min_dist;
            }
            else if (words[idx] == word2) {
                p2 = idx;
                min_dist = (p1 != -1)? min(min_dist, abs(p1-p2)): min_dist;
            }
        }
        
        return min_dist;
    }
};