Preprocess Word Positions for Repeated Distance Queries
Company: Palantir
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Implement WordDistance(wordsDict) and shortest(word1,word2). Each shortest call returns the least index distance between occurrences of its two different words in the original stored dictionary. Preserve this constructor and repeated-query API.
```cpp
class WordDistance {
public:
WordDistance(vector<string>& wordsDict);
int shortest(string word1, string word2);
};
```
### Examples
```text
WordDistance(["sun","rain","wind","sun","rain"]); shortest("sun","rain") -> 1; shortest("wind","sun") -> 1
WordDistance(["a","b","c"]); shortest("a","c") -> 2
```
### Constraints
- Dictionary length is 1 through 30000; words and targets have 1 through 10 lowercase letters.
- Every queried pair consists of distinct words present in the dictionary.
- At most 5000 shortest calls occur.
Overview: Preprocess Word Positions for Repeated Distance Queries. Implement WordDistance(wordsDict) and shortest(word1,word2). Each shortest call returns the least index distance between occurrences of its two different words