Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
- You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
For example,
- Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
- Given word1 = “coding”, word2 = “practice”, return 3.
- Given word1 = "makes", word2 = "coding", return 1.
Python Solution 1:
class Solution(object):
def shortestDistance(self, words, word1, word2):
"""
:type words: List[str]
:type word1: str
:type word2: str
:rtype: int
"""
w1pos = -1
w2pos = -1
res = len(words)
for i in range(len(words)):
if word1 == words[i]:
w1pos = i
if w2pos != -1:
res = min(res, w1pos - w2pos)
elif word2 == words[i]:
w2pos = i
if w1pos != -1:
res = min(res, w2pos - w1pos)
return res
Python Solution 2:
class Solution(object):
def shortestDistance(self, words, word1, word2):
"""
:type words: List[str]
:type word1: str
:type word2: str
:rtype: int
"""
last = -1
res = len(words)
for i, word in enumerate(words):
if word == word1 or word == word2:
if last != -1 and word != words[last]:
res = min(res, i - last)
last = i
return res
Summary:
- Solution 2 is much better.
LeetCode: 243. Shortest Word Distance
近期评论