# Python O(n*n) solution with comments.

• ``````# 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/longest-palindromic-substring/
def helper(self, words, i, word2):
j = 0
while (i-j<0 or words[i-j]!=word2) and (i+j>=len(words) or words[i+j]!=word2):
j += 1
return j``````

• 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(i-j) for i in ind1 for j in ind2)``````

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