摘要：代碼第一次寫入就先不比較第一次寫入就先不比較哈希表法復(fù)雜度時間空間思路因為會多次調(diào)用，我們不能每次調(diào)用的時候再把這兩個單詞的下標找出來。我們可以用一個哈希表，在傳入字符串?dāng)?shù)組時，就把每個單詞的下標找出存入表中。

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

時間 O(N) 空間 O(1)

一個指針指向word1上次出現(xiàn)的位置，一個指針指向word2上次出現(xiàn)的位置。因為兩個單詞如果比較接近的話，肯定是相鄰的word1和word2的位置之差，所以我們只要每次得到一個新位置和另一個單詞的位置比較一下就行了。

public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int idx1 = -1, idx2 = -1, distance = Integer.MAX_VALUE;
        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)){
                idx1 = i;
                // 第一次寫入idx就先不比較
                if(idx2 != -1) distance = Math.min(distance, idx1 - idx2);
            }
            if(words[i].equals(word2)){
                idx2 = i;
                // 第一次寫入idx就先不比較
                if(idx1 != -1) distance = Math.min(distance, idx2 - idx1);
            }
        }
        return distance;
    }
}

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?
Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.
For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.
Note: You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

時間 O(N) 空間 O(N)

因為會多次調(diào)用，我們不能每次調(diào)用的時候再把這兩個單詞的下標找出來。我們可以用一個哈希表，在傳入字符串?dāng)?shù)組時，就把每個單詞的下標找出存入表中。這樣當(dāng)調(diào)用最短距離的方法時，我們只要遍歷兩個單詞的下標列表就行了。具體的比較方法，則類似merge two list，每次比較兩個list最小的兩個值，得到一個差值。然后把較小的那個給去掉。因為我們遍歷輸入數(shù)組時是從前往后的，所以下標列表也是有序的。

public class WordDistance {
    
    HashMap> map = new HashMap>();
    
    public WordDistance(String[] words) {
        // 統(tǒng)計每個單詞出現(xiàn)的下標存入哈希表中
        for(int i = 0; i < words.length; i++){
            List cnt = map.get(words[i]);
            if(cnt == null){
                cnt = new ArrayList();
            }
            cnt.add(i);
            map.put(words[i], cnt);
        }
    }

    public int shortest(String word1, String word2) {
        List idx1 = map.get(word1);
        List idx2 = map.get(word2);
        int distance = Integer.MAX_VALUE;
        int i = 0, j = 0;
        // 每次比較兩個下標列表最小的下標，然后把跳過較小的那個
        while(i < idx1.size() && j < idx2.size()){
            distance = Math.min(Math.abs(idx1.get(i) - idx2.get(j)), distance);
            if(idx1.get(i) < idx2.get(j)){
                i++;
            } else {
                j++;
            }
        }
        return distance;
    }
}

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “makes”, word2 = “coding”, return 1. Given word1 = "makes", word2 = "makes", return 3.
Note: You may assume word1 and word2 are both in the list.

時間 O(N) 空間 O(N)

這題和I是一樣的，唯一不同的是對于word1和word2相同的時候，我們要區(qū)分第一次遇到和第二次遇到這個詞。這里加入了一個turns，如果是相同單詞的話，每次遇到一個單詞turn加1，這樣可以根據(jù)turn來判斷是否要switch。

public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int idx1 = -1, idx2 = -1, distance = Integer.MAX_VALUE, turn = 0, inc = (word1.equals(word2) ? 1 : 0);
        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1) && turn % 2 == 0){
                idx1 = i;
                if(idx2 != -1) distance = Math.min(distance, idx1 - idx2);
                turn += inc;
            } else if(words[i].equals(word2)){
                idx2 = i;
                if(idx1 != -1) distance = Math.min(distance, idx2 - idx1);
                turn += inc;
            }
        }
        return distance;
    }
}