Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
word1 and word2 may be the same and they represent two individual words in the list.
Note:
This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
classSolution(object):defshortestDistance(self,words,word1,word2):""" :type words: List[str] :type word1: str :type word2: str :rtype: int """ p1, p2 = [], []# find position for word1 and word2for i inrange(len(words)):if words[i]== word1: p1.append(i)if words[i]== word2:# use if instead of elif p2.append(i)# find shortest distance distance =len(words)for i in p1:for j in p2:if i != j:# don't update when i = j distance =min(distance, abs(i-j))return distance
Idea 2 (greedy)
If word1 is not the same as word2, update shortest distance for each new location when we scan from left to right.
If word1 is the same as word2, only update the shortest distance for new location of word1.
Complexity 2
Solution 2
classSolution(object):defshortestDistance(self,words,word1,word2):""" :type words: List[str] :type word1: str :type word2: str :rtype: int """ n =len(words) distance = n p1 = p2 =-nfor i inrange(n):if words[i]== word1: p1 = i distance =min(distance, i - p2)if words[i]== word2:# use if instead of elif p2 = iif word1 != word2:# new line distance =min(distance, i - p1)# new linereturn distance