这几题都挺没意思的，建一个hashMap，里面存放出现过的位置的list

short稍微有点讲究，就是不要两个都重头找一遍，每次只移动小的那个

 

1 public class WordDistance { 2     Map
     
      > map; 3  4     public WordDistance(String[] words) { 5         map = new HashMap
      
       >(); 6         for(int i = 0; i < words.length; i++) { 7             if(map.containsKey(words[i])) { 8                 List
       
         cur = map.get(words[i]); 9                 cur.add(i);10                 map.put(words[i], cur);11             } else {12                 List
        
          cur = new ArrayList
         
          ();13                 cur.add(i);14                 map.put(words[i], cur);15             }16         }17     }18 19     public int shortest(String word1, String word2) {20         List
          
            list1 = map.get(word1);21 List
           
             list2 = map.get(word2);22 int i = 0; 23 int j = 0;24 int min = Integer.MAX_VALUE;25 while(i < list1.size() && j < list2.size()) {26 min = Math.min(min, Math.abs(list1.get(i) - list2.get(j)));27 if(list1.get(i) < list2.get(j)) {28 i++;29 } else {30 j++;31 }32 } 33 return min;34 }35 }36 37 // Your WordDistance object will be instantiated and called as such:38 // WordDistance wordDistance = new WordDistance(words);39 // wordDistance.shortest("word1", "word2");40 // wordDistance.shortest("anotherWord1", "anotherWord2");