[LeetCode] Shortest Word Distance II

简介: Problem Description: This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will b...

Problem Description:

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = "coding”word2 = "practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.


The key idea is to store the indexes of each word using a hash map. Then the function shortest() is just to find the minimum difference between two sorted lists (see here for a method).

The code is as follows.

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

 

目录
相关文章
LeetCode 318. Maximum Product of Word Lengths
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
65 0
LeetCode 318. Maximum Product of Word Lengths
LeetCode 290. Word Pattern
给定一种 pattern(模式) 和一个字符串 str ,判断 str 是否遵循相同的模式。 这里的遵循指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。
35 0
LeetCode 290. Word Pattern
LeetCode 212. Word Search II
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
64 0
LeetCode 212. Word Search II
|
索引
LeetCode 79. Word Search
给定一个2D板和一个单词,找出该单词是否存在于网格中。 该单词可以由顺序相邻的单元的字母构成,其中“相邻”单元是水平或垂直相邻的单元。 相同的字母单元格不得多次使用。
56 0
LeetCode 79. Word Search