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.
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)