LeetCode Shortest Word Distance II

原题链接在这里：https://leetcode.com/problems/shortest-word-distance-ii/

题目：

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

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.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

题解：

method 会被call好多次，没有必要每次都traverse 一遍words array. 简历一个HashMap, key是word, value是该word出现index的list.

双指针遍历word1 和 word2 两个index list 计算最小距离.

Time Complexity: Constructor WordDistance O(words.length). shortest O(list1.size()+list2.size()).

Space: O(words.length).

AC Java:

 public class WordDistance {

     HashMap<String, List<Integer>> hm;

     public WordDistance(String[] words) {

         hm = new HashMap<String, List<Integer>>();

         for(int i = 0; i<words.length; i++){

             if(!hm.containsKey(words[i])){

                 List<Integer> ls = new ArrayList<Integer>();

                 hm.put(words[i], ls);

             }

             hm.get(words[i]).add(i);

         }

     }

     public int shortest(String word1, String word2) {

         List<Integer> l1 = hm.get(word1);

         List<Integer> l2 = hm.get(word2);

         int res = Integer.MAX_VALUE;

         int i = 0;

         int j = 0;

         while(i<l1.size() && j<l2.size()){

             int index1 = l1.get(i);

             int index2 = l2.get(j);

             if(index1<index2){

                 res = Math.min(res, index2-index1);

                 i++;

             }else{

                 res = Math.min(res, index1-index2);

                 j++;

             }

         }

         return res;

     }

 }

 // Your WordDistance object will be instantiated and called as such:

 // WordDistance wordDistance = new WordDistance(words);

 // wordDistance.shortest("word1", "word2");

 // wordDistance.shortest("anotherWord1", "anotherWord2");

类似Shortest Word Distance.

跟上Shortest Word Distance III.

巴特西

LeetCode Shortest Word Distance II

最新文章

热门文章