题目地址：

https://www.lintcode.com/problem/926/

给定一个长 n n n的字符串数组 A A A，再给定两个单词 w 1 w_1 w1​和 w 2 w_2 w2​，问在 A A A里它们的最短距离。题目不保证 w 1 w_1 w1​和 w 2 w_2 w2​不同，但保证它们都出现过。如果 w 1 = w 2 w_1=w_2 w1​=w2​，那么最短距离就定义为它们相邻的两次出现的最短距离。

开两个指针 i 1 i_1 i1​和 i 2 i_2 i2​，分别指向两个单词相邻的两次出现。遍历 A A A，并维护两个指针的定义，关键在于 w 1 = w 2 w_1=w_2 w1​=w2​的情况，此时两个指针分别维护的是前一次出现和当前出现，所以要将 i 2 i_2 i2​赋值给 i 1 i_1 i1​，然后再将当前所处位置赋值给 i 2 i_2 i2​。代码如下：

public class Solution {
    /**
     * @param words: a list of words
     * @param word1: a string
     * @param word2: a string
     * @return: the shortest distance between word1 and word2 in the list
     */
    public int shortestWordDistance(String[] words, String word1, String word2) {
        // Write your code here
        int res = Integer.MAX_VALUE, idx1 = -1, idx2 = -1;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                idx1 = i;
            }
            if (words[i].equals(word2)) {
                if (word1.equals(word2)) {
                    idx1 = idx2;
                }
                idx2 = i;
            }
            
            if (idx1 != -1 && idx2 != -1) {
                res = Math.min(res, Math.abs(idx1 - idx2));
            }
        }
        
        return res;
    }
}

时间复杂度 O ( n l ) O(nl) O(nl)，空间 O ( 1 ) O(1) O(1)， l l l是两个字符串的最长长度。