243_Shortest Word Distance
243. Shortest Word Distance
Level: easy
Tag: array
Question
Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Example1
Input: words = ["practice", "makes", "perfect", "coding", "makes"]
word1 = “coding”
word2 = “practice”
Output: 3
Idea 1 (brute force)
Find all the positions for word1 and word2, and compute the shortest distance by minimizing .
Complexity 1
Time: where is the length of the array and is the maximum number of word1 and word2.
Space:
Solution 1
class Solution(object):
def shortestDistance(self, words, word1, word2):
"""
:type words: List[str]
:type word1: str
:type word2: str
:rtype: int
"""
p1, p2 = [], []
# find position for word1 and word2
for i in range(len(words)):
if words[i] == word1:
p1.append(i)
elif words[i] == word2:
p2.append(i)
# find shortest distance
distance = len(words)
for i in p1:
for j in p2:
distance = min(distance, abs(i-j))
return distance
Idea 2 (greedy)
Keep two indices where we store the most recent locations of word1 and word2. Update shortest distance when we scan from left to right.
Complexity 2
Time: where is the length of the array
Space:
Solution 2
class Solution(object):
def shortestDistance(self, words, word1, word2):
"""
:type words: List[str]
:type word1: str
:type word2: str
:rtype: int
"""
n = len(words)
distance = n
p1 = p2 = -n
for i in range(n):
if words[i] == word1:
p1 = i
distance = min(distance, i - p2)
elif words[i] == word2:
p2 = i
distance = min(distance, i - p1)
return distance
Last updated
Was this helpful?