Java faster than 100% solutions (14ms) no magic here


  • 0
    B
    public class WordDistance {
    
        private final Map<String, List<Integer>> indices = new HashMap<>();
    
        public WordDistance(String[] words) {
          for(int i = 0; i < words.length; i++) {
            String word = words[i];
            List<Integer> indicesForWord = indices.get(word);
            if(indicesForWord == null) {
              indicesForWord = new ArrayList<>();
              indices.put(word, indicesForWord);
            }
            indicesForWord.add(i);
          }
        }
    
        public int shortest(String word1, String word2) {
          int min = Integer.MAX_VALUE;
          int i = 0, j = 0;
          List<Integer> indices1 = indices.get(word1);
          List<Integer> indices2 = indices.get(word2);
          while(i < indices1.size() && j < indices2.size()) {
            min = Math.min(min, Math.abs(indices2.get(j) - indices1.get(i)));
            if(i + 1 == indices1.size() || indices2.get(j) < indices1.get(i)) j++;
            else i++;
          }
          return min;
        }
    
      }
    

    Time for initialization/indexing: O(n)
    Time for finding distance: O(n)
    Memory: O(n)


Log in to reply
 

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