# O(n*n) time
def shortestDistance(self, words, word1, word2):
res = len(words)
for i in xrange(len(words)):
if words[i] == word1:
res = min(res, self.helper(words, i, word2))
return res
# go from middle point to both sides,
# like: https://leetcode.com/problems/longestpalindromicsubstring/
def helper(self, words, i, word2):
j = 0
while (ij<0 or words[ij]!=word2) and (i+j>=len(words) or words[i+j]!=word2):
j += 1
return j
Python O(n*n) solution with comments.


Here is a version which stores the indexes:
# O(n*n) time, O(n) space def shortestDistance(self, words, word1, word2): ind1, ind2 = [], [] for i, w in enumerate(words): if w == word1: ind1.append(i) elif w == word2: ind2.append(i) # return min(map(lambda x: abs(x[0]x[1]), itertools.product(ind1, ind2))) # return min(map(lambda x: abs(x[0]x[1]), ((i, j) for i in ind1 for j in ind2))) return min(abs(ij) for i in ind1 for j in ind2)