?LeetCode刷題實(shí)戰(zhàn)244：最短單詞距離 II

示例:
假設(shè) words = ["practice", "makes", "perfect", "coding", "makes"]

輸入: word1 = “coding”, word2 = “practice”
輸出: 3
輸入: word1 = "makes", word2 = "coding"
輸出: 1

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

    public int shortest(String word1, String word2) {
        List<Integer> idx1 = map.get(word1);
        List<Integer> idx2 = map.get(word2);
        int distance = Integer.MAX_VALUE;
        int i = 0, j = 0;
        // 每次比較兩個(gè)下標(biāo)列表最小的下標(biāo)，然后把跳過較小的那個(gè)
        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;
    }
}