WAP to Given any two words, find the shortest distance (in terms of number of words) between them in the file.

You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. Can you make the searching operation in O(1) time? What about the space complexity for your solution?


We will assume for this question that the word order does not matter. This is a question you should ask your interviewer. If the word order does matter, we can make the small modification
shown in the code below.

class min_dist_two_words
{
public static void main(String a[])
{

System.out.println(shortest(new String[]{"abc","def","gh","cd","fe"},"gh","fe"));

}
static int shortest(String[] words, String word1, String word2)
{
int pos = 0;
int min = Integer.MAX_VALUE / 2;
int word1_pos = -min;
int word2_pos = -min;
for (int i = 0; i < words.length; i++) {
String current_word = words[i];
if (current_word.equals(word1)) {
word1_pos = pos;
// Comment following 3 lines if word order matters
int distance = word1_pos - word2_pos;
if (min > distance)
min = distance;
} else if (current_word.equals(word2)) {
word2_pos = pos;
int distance = word2_pos - word1_pos;
if (min > distance) min = distance;
}
++pos;
}
return min;
}

}


Time Complexity O(n)
Space Complexity O(1)


To solve this problem in less time (but more space), we can create a hash table with each word and the locations where it occurs. We then just need to find the minimum (arithmetic) difference in the locations (e.g., abs(word0.loc[1] - word1.loc[5])).
To find the minimum arithmetic difference, we take each location for word1 (e.g.: 0, 3} and do a modified binary search for it in word2’s location list, returning the closest number. Our search for 3, for example, in {2, 7, 9} would return 1. The minimum of all these binary searches is the shortest distance.

Time Complexity O(1)
Space Complexity O(n)

Soln Provided By Gayle