LeetCode(115) -- 244, 245

P244. Shortest Word Distance II (Medium)

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. Your method will be called repeatedly many times with different parameters.

My Solution

class WordDistance {

    HashMap<String, List<Integer>> map;
    public WordDistance(String[] words) {
        map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            List<Integer> list = map.getOrDefault(words[i], new ArrayList<>());
            list.add(i);
            map.put(words[i], list);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        int i = 0, j = 0;
        int size1 = list1.size();
        int size2 = list2.size();
        int shortest = Integer.MAX_VALUE;
        while (i < size1 && j < size2) {
            Integer curr1 = list1.get(i);
            Integer curr2 = list2.get(j);
            if (curr1 < curr2) {
                shortest = Math.min(shortest, curr2 - curr1);
                i++;
            } else {
                shortest = Math.min(shortest, curr1 - curr2);
                j++;
            }
        }
        return shortest;
    }
}

99%

Solution

class WordDistance {

    HashMap<String, ArrayList<Integer>> locations;

    public WordDistance(String[] words) {
        this.locations = new HashMap<String, ArrayList<Integer>>();

        // Prepare a mapping from a word to all it's locations (indices).
        for (int i = 0; i < words.length; i++) {
            ArrayList<Integer> loc = this.locations.getOrDefault(words[i], new ArrayList<Integer>());
            loc.add(i);
            this.locations.put(words[i], loc);
        }
    }

    public int shortest(String word1, String word2) {
        ArrayList<Integer> loc1, loc2;

        // Location lists for both the words
        // the indices will be in SORTED order by default
        loc1 = this.locations.get(word1);
        loc2 = this.locations.get(word2);

        int l1 = 0, l2 = 0, minDiff = Integer.MAX_VALUE;
        while (l1 < loc1.size() && l2 < loc2.size()) {
            minDiff = Math.min(minDiff, Math.abs(loc1.get(l1) - loc2.get(l2)));
            if (loc1.get(l1) < loc2.get(l2)) {
                l1++;
            } else {
                l2++;
            }
        }

        return minDiff;
    }
}

思路基本一样。

P245. Shortest Word Distance III (Medium)

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.

My Solution

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        HashMap<String, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            List<Integer> list = map.getOrDefault(words[i], new ArrayList<>());
            list.add(i);
            map.put(words[i], list);
        }
        List<Integer> list1 = map.get(word1);
        List<Integer> list2 = map.get(word2);
        int i = 0, j = 0;
        int size1 = list1.size();
        int size2 = list2.size();
        int shortest = Integer.MAX_VALUE;
        while (i < size1 && j < size2) {
            Integer curr1 = list1.get(i);
            Integer curr2 = list2.get(j);
            if (curr1 < curr2) {
                shortest = Math.min(shortest, curr2 - curr1);
                i++;
            } else if (curr1 > curr2) {
                shortest = Math.min(shortest, curr1 - curr2);
                j++;
            } else {
                i++;
            }
        }
        return shortest;
    }
}

21%

The Best Solution

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        Set<Integer>word1Indices = new HashSet<>();
        Set<Integer>word2Indices = new HashSet<>();
        for (int i=0;i<words.length;i++){
            if (words[i].equals(word1))word1Indices.add(i);
            if (words[i].equals(word2))word2Indices.add(i);
        }
        int min = Integer.MAX_VALUE;
        for (int i:word1Indices){
            for (int j:word2Indices){
                if (i!=j) min = Math.min(min, Math.abs(i-j));
            }
        }
        return min;
    }
}

这次不用HashMap了。