My Java solution


  • 0
    W
    class WordDistance {
        Map<String, List<Integer>> map;
        public WordDistance(String[] words) {
            map = new HashMap<String, List<Integer>>();
            for (int i = 0; i < words.length; i ++) {
                List<Integer> positions = map.getOrDefault(words[i], new ArrayList<Integer>());
                positions.add(i);
                map.put(words[i], positions);
            }
        }
        
        public int shortest(String word1, String word2) {
            List<Integer> positions1 = map.get(word1);
            List<Integer> positions2 = map.get(word2);
            
            int min = Integer.MAX_VALUE;
            
            int j = 0;
            for (int i = 0; i < positions1.size(); i ++) {
                int p1 = positions1.get(i);
                while (j < positions2.size()) {
                    int p2 = positions2.get(j);
                    min = Math.min(min, Math.abs(p1 - p2));
                    if (p2 > p1) break;
                    j ++;
                }
            }
            return min;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.