Comment on page

# 243 Shortest Word Distance

Given a list of words and two wordsword1andword2, return the shortest distance between these two words in the list.
For example, Assume that words =`["practice", "makes", "perfect", "coding", "makes"]`.
Givenword1=`“coding”`,word2=`“practice”`, return 3. Givenword1=`"makes"`,word2=`"coding"`, return 1.
Note: You may assume thatword1does not equal toword2, andword1andword2are both in the list.
Attempt 1
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
int shortestDistance(vector<string> *words, string word1, string word2)
{
vector<int> minElements;
vector<int> word1Positions;
vector<int> word2Positions;
int word1Pos, word2Pos;
int size = (*words).size();
for (int i = 0; i < size; i++)
{
// store all positions of first word
string currentWord = (*words).at(i);
if (currentWord == word1)
word1Positions.push_back(i);
else if(currentWord == word2)
word2Positions.push_back(i);
}
// find the minimum displacement between each word
int difference;
int j = 0;
while (word2Positions.size() > j)
{
for (int i = 0; i < word1Positions.size(); i++)
{
difference = abs(((word1Positions).at(i)) - ((word2Positions).at(j)));
minElements.push_back(difference);
}
j++;
}
int minElement = *min_element(minElements.begin(), minElements.end());
cout << minElement << endl;
return minElement;
}
int main()
{
vector<string> words = { "practice", "makes", "perfect", "coding", "makes" };
string word1 = "coding", word2 = "practice"; // 3
string word3 = "makes", word4 = "coding"; // 1
shortestDistance(&words, word1, word2);
shortestDistance(&words, word3, word4);
}
Attempt 2: (12 ms, 92 percentile)
The Idea: First locate the occurrences of both words into two arrays. The shortest difference would then just be the minimum absolute difference between these two arrays. More specifically, it would be the minimum pair wise combination between the two arrays. We can perform two improvements here: first, since the arrays are sorted, we can binary search for the minimum difference. Secondly, we can scale better if we binary search on the larger array group. We know that we found the minimum difference when both the left and right side of the element produce a larger difference with the current key.
Complexity: O(NlogN) time, O(N) space
template<typename T>
int binary_search(vector<T> &nums, int low, int high, const T key, int prev_sol) {
// if nothing was found then that means an equidistant element was ignored
if (high < low) return prev_sol;
int median = low + ((high - low) / 2);
int med = nums.at(median);
int left = median - 1 >= 0 ? nums.at(median - 1) : INT_MAX;
int right = median + 1 < nums.size() ? nums.at(median + 1) : INT_MAX;
int cur_diff = abs(med - key);
// the center difference is smaller than both left and right differences
// left and right are open
if (left != INT_MAX && right != INT_MAX) {
if (cur_diff < med - left && cur_diff < right - med)
return cur_diff;
// if the difference is smaller with the left element, then
// we are bound to find a better improvement on the left
if (abs(left - key) < cur_diff) {
return binary_search(nums, low, median - 1, key, cur_diff);
}
// otherwise a word from the right must be closer
else return binary_search(nums, median + 1, high, key, cur_diff);
}
// left is not open, right is
else if (left == INT_MAX && right != INT_MAX) {
if (cur_diff < abs(right - key))
return cur_diff;
return binary_search(nums, median + 1, high, key, cur_diff);
}
// left is open, right is not
else if (left != INT_MAX && right == INT_MAX) {
if (cur_diff < abs(left - key))
return cur_diff;
return binary_search(nums, low, median - 1, key, cur_diff);
}
// both left and right are closed
else if (left == INT_MAX && right == INT_MAX) {
return cur_diff;
}
}
int shortestDistance(vector<string>& words, string word1, string word2) {
// store positions of target words
vector<int> word1_pos, word2_pos;
int counter = 0;
for (string s : words) {
if (s == word1) {
word1_pos.push_back(counter);
}
else if (s == word2) {
word2_pos.push_back(counter);
}
counter++;
}
// find the smallest absolute difference between every
// pair wise combination of two vectors
int cur_min = INT_MAX;
if (word1_pos.size() < word2_pos.size())
for (int i : word1_pos) {
int closest_word_index = binary_search(word2_pos, 0, word2_pos.size() - 1, i, -1);
cur_min = min(cur_min, closest_word_index);
}
else
for (int i : word2_pos) {
int closest_word_index = binary_search(word1_pos, 0, word1_pos.size() - 1, i, -1);
cur_min = min(cur_min, closest_word_index);
}
return cur_min;
}
Testing
int main()
{
vector<string> words = { "practice", "makes", "perfect", "coding", "makes" };
cout << shortestDistance(words, "coding", "practice") << endl; // 3
cout << shortestDistance(words, "makes", "coding") << endl; // 1
vector<string> words1 = { "b", "practice","practice","b", "practice", "makes", "perfect","makes", "coding", "makes", "a" };
cout << shortestDistance(words1, "a", "b") << endl; // 7
cout << shortestDistance(words1, "practice", "coding") << endl; // 4
vector<string> words2 = { "a", "c", "b", "b", "a" };
cout << shortestDistance(words2, "a", "b") << endl; // 1
}