Leetcode #243. Shortest Word Distance

[yokostan]

My solution, very slow, beats 8%:

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        HashMap<String, ArrayList<Integer>> map = new HashMap<>();
        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);
        }

        ArrayList<Integer> l1 = map.get(word1);
        ArrayList<Integer> l2 = map.get(word2);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < l1.size(); i++) {
            for (int j = 0; j < l2.size(); j++) {
                res = Math.min(res, Math.abs(l1.get(i) - l2.get(j)));
            }
        }

        return res;
    }
}

Here is a smart one:

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
    //Brute force would take O(n)
    //Smart idea: store the most recent indexes of word1 and word2. When we meet word1/word2, we try to update the min
        int pre1 = -1;
        int pre2 = -1;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < words.length; i++)
        {

            if(words[i].equals(word1))
            {
                if(pre2!=-1)
                    min = Math.min(i-pre2, min);
                pre1 = i;
            }

            if(words[i].equals(word2))
            {
                if(pre1!=-1)
                    min = Math.min(i-pre1, min);
                pre2 = i;
            }
        }
        return min;   
    }
}