Solution: Shortest Word Distance II
Explore designing the WordDistance class to efficiently calculate the shortest distance between two given words in a string array. Understand how preprocessing with a dictionary of word indices and a two-pointer traversal method reduce query time complexity. This lesson demonstrates building and querying the data structure with O(n) construction and O(m+n) query time for multiple shortest distance calls.
We'll cover the following...
Statement
Design a data structure that takes in an array of strings and efficiently computes the shortest distance between any two different strings in the array.
Implement the WordDistance class:
WordDistance(String[] wordsDict): Initializes the object with an array of strings.int shortest(String word1, String word2): Returns the shortest distance betweenword1andword2in the array of strings.
Constraints:
wordsDict.length...