LIKE CODING: LeetCode [243] Shortest Word Distance

http://sbzhouhao.net/LeetCode/LeetCode-Shortest-Word-Distance.html

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.

http://www.tangjikai.com/algorithms/leetcode-243-shortest-word-distance

1. def shortestDistance(self, words, word1, word2):
2. a = b = -1
3. ans = len(words)
5. for i in range(len(words)):
6. if words[i] == word1:
7. a = i
8. elif words[i] == word2:
9. b = i
11. if a >= 0 and b >= 0:
12. ans = min(ans, abs(a - b))
13. return ans

LIKE CODING: LeetCode [243] Shortest Word Distance

    int shortestDistance(vector<string>& words, string word1, string word2) {

        int n = words.size();

        int p1 = -1, p2 = -1, dist = INT_MAX;

        for(int i=0; i<n; ++i){

            if(words[i]==word1) p1 = i;

            if(words[i]==word2) p2 = i;

            if(p1>=0 && p2>=0)

                dist = min(dist, abs(p1-p2));

        }

        return dist;

    }

X. Not efficient

    public int shortestDistance(String[] words, String word1, String word2) {
        Map<String, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < words.length; i++) {
            String s = words[i];
            List<Integer> list;
            if (map.containsKey(s)) {
                list = map.get(s);
            } else {
                list = new ArrayList<>();
            }
            list.add(i);
            map.put(s, list);
        }
        List<Integer> l1 = map.get(word1);
        List<Integer> l2 = map.get(word2);

        int min = Integer.MAX_VALUE;

        for (int a : l1) {
            for (int b : l2) {
                min = Math.min(Math.abs(b - a), min);
            }
        }

        return min;
    }

Read full article from LIKE CODING: LeetCode [243] Shortest Word Distance