Welcome to Subscribe On Youtube

244. Shortest Word Distance II

Description

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

  • WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
  • int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

 

Example 1:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

 

Constraints:

  • 1 <= wordsDict.length <= 3 * 104
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are in wordsDict.
  • word1 != word2
  • At most 5000 calls will be made to shortest.

Solutions

Constructor: __init__

  • A dictionary self.d is initialized using defaultdict(list) from the collections module. This allows for appending indices to lists for each word without needing to check if the key exists.
  • The constructor iterates over wordsDict, enumerating each word w along with its index i. Each word’s index is appended to its corresponding list in self.d. This setup facilitates quick access to all positions where each word appears in the list, crucial for efficiently calculating the distance between any two words later on.

Method: shortest

  • Given two words, word1 and word2, the method retrieves their respective index lists (a and b) from self.d.
  • It initializes ans with inf (infinity) to ensure that any actual distance found will be smaller than this initial value.
  • Two pointers, i and j, are initialized to iterate over the index lists a and b, respectively.
  • The method enters a loop that continues until either i or j has traversed its entire list. Inside the loop:
    • The absolute difference between the current indices a[i] and b[j] is calculated and used to update ans if it’s smaller than the current value of ans. This step finds the minimum distance between the current pair of indices.
    • The pointer (i or j) corresponding to the smaller index is incremented. If a[i] is less than or equal to b[j], i is incremented; otherwise, j is incremented. This approach ensures that the loop efficiently finds the minimum distance by always moving the pointer that points to the smaller index, thereby reducing the difference in the next iteration.
  • Once the loop completes, ans holds the minimum distance found between any pair of indices from a and b.

Example

Consider wordsDict = ["practice", "makes", "perfect", "coding", "makes"], and we want to find the shortest distance between "coding" and "makes":

  • self.d["coding"] = [3], and self.d["makes"] = [1, 4].
  • The shortest distance calculation checks the differences abs(3 - 1) = 2 and abs(3 - 4) = 1.
  • The minimum distance is 1, so ans = 1.

This class provides an efficient way to find the shortest distance between two words in a list, optimizing for cases where multiple queries are made against the same list by preprocessing the list into a more accessible form.

  • class WordDistance {
    private Map<String, List<Integer>> d = new HashMap<>();

    public WordDistance(String[] wordsDict) {
        for (int i = 0; i < wordsDict.length; ++i) {
            d.computeIfAbsent(wordsDict[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> a = d.get(word1), b = d.get(word2);
        int ans = 0x3f3f3f3f;
        int i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            ans = Math.min(ans, Math.abs(a.get(i) - b.get(j)));
            if (a.get(i) <= b.get(j)) {
                ++i;
            } else {
                ++j;
            }
        }
        return ans;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(wordsDict);
 * int param_1 = obj.shortest(word1,word2);
 */

  • class WordDistance {
public:
    WordDistance(vector<string>& wordsDict) {
        for (int i = 0; i < wordsDict.size(); ++i) {
            d[wordsDict[i]].push_back(i);
        }
    }

    int shortest(string word1, string word2) {
        auto a = d[word1], b = d[word2];
        int i = 0, j = 0;
        int ans = INT_MAX;
        while (i < a.size() && j < b.size()) {
            ans = min(ans, abs(a[i] - b[j]));
            if (a[i] <= b[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        return ans;
    }

private:
    unordered_map<string, vector<int>> d;
};

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance* obj = new WordDistance(wordsDict);
 * int param_1 = obj->shortest(word1,word2);
 */

  • class WordDistance:
    def __init__(self, wordsDict: List[str]):
        self.d = defaultdict(list)
        for i, w in enumerate(wordsDict):
            self.d[w].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        a, b = self.d[word1], self.d[word2]
        ans = inf
        i = j = 0
        while i < len(a) and j < len(b):
            ans = min(ans, abs(a[i] - b[j]))
            if a[i] <= b[j]:
                i += 1
            else:
                j += 1
        return ans


# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(wordsDict)
# param_1 = obj.shortest(word1,word2)

############

class WordDistance(object):
  def __init__(self, words):
    """
    initialize your data structure here.
    :type words: List[str]
    """
    self.d = {}
    for i in range(0, len(words)):
      self.d[words[i]] = self.d.get(words[i], []) + [i]

  def shortest(self, word1, word2):
    """
    Adds a word into the data structure.
    :type word1: str
    :type word2: str
    :rtype: int
    """
    l1 = self.d[word1]
    l2 = self.d[word2]
    i = j = 0
    ans = float("inf")
    while i < len(l1) and j < len(l2):
      ans = min(ans, abs(l1[i] - l2[j]))
      if l1[i] > l2[j]:
        j += 1
      else:
        i += 1
    return ans

# Your WordDistance object will be instantiated and called as such:
# wordDistance = WordDistance(words)
# wordDistance.shortest("word1", "word2")
# wordDistance.shortest("anotherWord1", "anotherWord2")


  • type WordDistance struct {
	d map[string][]int
}

func Constructor(wordsDict []string) WordDistance {
	d := map[string][]int{}
	for i, w := range wordsDict {
		d[w] = append(d[w], i)
	}
	return WordDistance{d}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
	a, b := this.d[word1], this.d[word2]
	ans := 0x3f3f3f3f
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		ans = min(ans, abs(a[i]-b[j]))
		if a[i] <= b[j] {
			i++
		} else {
			j++
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * obj := Constructor(wordsDict);
 * param_1 := obj.Shortest(word1,word2);
 */

All Problems

All Solutions