244. Shortest Word Distance II

// LeetCode URL: https://leetcode.com/problems/shortest-word-distance-ii/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Create a map of each word and its index in words array. Now compare this
 * index lists of 2 words to find the minimum distance.
 *
 * Time Complexity: WordDistance Constructor = O(L * N). shortest function = O(I
 * + J) = O(N). I = Length of indexList1. J = Length of indexList2. In worst
 * case sum of I & J will be N.
 *
 * Space Complexity: O(L * N). Size of the map.
 *
 * L = Average length of a word in words array. N = Number words in the input
 * array.
 */
class WordDistance {

    HashMap<String, List<Integer>> map;

    public WordDistance(String[] words) {
        map = new HashMap<>();
        if (words == null || words.length == 0) {
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {
                map.put(words[i], new ArrayList<Integer>());
            }
            map.get(words[i]).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        if (word1 == null || word2 == null || !map.containsKey(word1) || !map.containsKey(word2)) {
            return -1;
        }
        if (word1.equals(word2)) {
            return 0;
        }

        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);

        int result = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        while (i < list1.size() && j < list2.size()) {
            int index1 = list1.get(i);
            int index2 = list2.get(j);
            if (index1 < index2) {
                result = Math.min(result, index2 - index1);
                i++;
            } else {
                result = Math.min(result, index1 - index2);
                j++;
            }
        }

        return result;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 *
 * WordDistance obj = new WordDistance(words);
 *
 * int param_1 = obj.shortest(word1,word2);
 */