题面

题目大意参考： https://www.lintcode.com/problem/925/

算法：双指针

1. 时间复杂度：$O(QNw)$. ($Q$为查询次数，$N$为单词列表大小，$w$为单词平均长度)
2. 空间复杂度：$O(1)$

public class WordDistance {
    final int INF = 0x3f3f3f3f;
    List<String> dict;
    public WordDistance(List<String> wordsDict) {
        dict = wordsDict;
    }

    /**
     * @param word1: word1
     * @param word2: word2
     * @return: the shortest distance between two words
     */
    public int shortest(String word1, String word2) {
        int p = -1, q = -1, ans = INF, i = 0;
        for(String word : dict) {
            if(word.equals(word1)) {
                p = i;
                if(q != -1) {
                    ans = Math.min(ans, p - q);
                }
            }
            if(word.equals(word2)) {
                q = i;
                if(p != -1) {
                    ans = Math.min(ans, q - p);
                }
            }
            i++;
        }
        return ans;
    }
}