244. Shortest Word Distance II

My first impression is the hash table. The key value pair is (word, index). Since there could be duplicate words, the index should be a vector. Then the problem becomes to find shortest distance in two sorted vector. We can have two pointers. Everytime, we move the pointer who points to a smaller index.

1:  class WordDistance {  
2:  private:  
3:    unordered_map<string, vector<int>> mp;   
4:  public:  
5:    WordDistance(vector<string>& words) {  
6:      for (int i = 0; i < words.size(); i++) {  
7:        mp[words[i]].push_back(i);  
8:      }  
9:    }  
10:    int shortest(string word1, string word2) {  
11:      int i = 0, j = 0, dist = INT_MAX;  
12:      int sz1 = mp[word1].size(), sz2 = mp[word2].size();  
13:      while (i < sz1 && j < sz2) {  
14:        dist = min(dist, abs(mp[word1][i]-mp[word2][j]));  
15:        mp[word1][i] < mp[word2][j] ? i++ : j++;  
16:      }  
17:      return dist;  
18:    }  
19:  };  
20:  // Your WordDistance object will be instantiated and called as such:  
21:  // WordDistance wordDistance(words);  
22:  // wordDistance.shortest("word1", "word2");  
23:  // wordDistance.shortest("anotherWord1", "anotherWord2");