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[] words_dict): Initializes the object with an array of strings.

• int shortest(String word1, String word2): Returns the shortest distance between word1 and word2 in the array of strings.

Constraints:

• $1 \leq$ words_dict.length $\leq10^3$

• $1 \leq$ words_dict[i].length $\leq 10$

• words_dict[i] consists of lowercase English letters

• word1 and word2 are in words_dict

• word1 != word2

• At most, $1000$ calls will be made to the shortest

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to better understand how to solve this problem.

Implement your solution in the following coding playground.