# Given a list of words, find the absolute minimum distance between two words.

• example input:
["a", "b", "c", "a", "d"]

example output:
min_distance("a", "c") = 1

explanation:
"c" is in index 2 and "a" is in index 0 and 3. |3 - 2| = 1

• I guess it's the same as the "Shortest Word Distance" problem, I have a solution here: https://leetcode.com/discuss/50234/ac-java-clean-solution, hope that helps.

• Here's my solution in python:
def distCal(str1,str2):
arr = ['the','world','is','xxx','so','yyu','so','fhgf','so','big']
i = 0
while (i <= len(arr)):
if (str1 in arr) and (str2 in arr):
x = arr.index(str1) + 1
y = arr.index(str2) + 1
print(str1,"is at:",x, str2,"is at:",y)

``````	else:
print("Not in list")

return print("distance :", y - x)
``````

distCal('world','so')

• @DWu39 The direct answer to the question is to iterate and find the minimum distance which runs in linear time `O(N)` where N is the number of words.

A variant of the problem is to solve it in sub-linear time ( `< O(N)`). To solve this, we can create a map of word vs its list of indices in the original string (or string array of words). Then upon each `findMinDistance(word1, word2)`, you have get the indices list of `word1` and `word2` in the map and find the minimum difference in the two lists. In other words, the original problem is reduced to solve a sub-problem: Given two arrays of integers, find the minimum difference. In our case, this will yield sub-linear time (`< O(N)`).

This variant of the solution is useful in scenarios of repeated use of `findMinDistance`.

• JavaScript O(n)

``````function findMinimumWordDistance(words, wordA, wordB) {
var wordAIndex = null;
var wordBIndex = null;
var minDinstance = null;

for (var i = 0, length = words.length; i < length; i++ ) {
if (words[i] === wordA) {
wordAIndex = i;
}

if (words[i] === wordB) {
wordBIndex = i;
}

if ( wordAIndex !== null && wordBIndex !== null ) {
var distance = Math.abs(wordAIndex - wordBIndex);
if(minDinstance === null || minDinstance > distance) {
minDinstance = distance;
}
}
}
return minDinstance;
}
``````

• @VivekRagunathan not necessarily. If we're given a long list that contains a small variation of words, each word's "index list" will have O(n) elements and, therefore, looking for a min between two arrays that have O(n) elements will cost O(n) time to process.

• is the distance between two words A and B is sum ( abs( ai - bi) ) for 0 <= i < len(A) + sum( bj ) for len(A) <= j < len(B) for len(A) <= len(B) ?

• words = ['a','b','c','a','d','e','b','f','a']

def min_dis(word1,word2,word_list):
dist1 = list()
dist2 = list()
dist = list()
for i,j in enumerate(words):
if j == word1:
dist1.append(i)
elif j == word2:
dist2.append(i)
dist = [abs(x -y) for x in dist1 for y in dist2]
return min(dist)

min_dis('a','e',words)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.