难度: Medium
Submission
运行时间: 68 ms
内存: 0.0 MB
class Solution:
def shortestWordDistance(self, words: List[str], word1: str, word2: str) -> int:
#和243一样，注意两个词一样的情况
if not words:
return None
index1,index2 = -1,-1
last_word = None
dist = len(words)+1
for i,word in enumerate(words):
#word1==word2的情况都在这里处理
if word == word1:
if (last_word and last_word==word2) or (last_word and word1==word2):
if word1!=word2:
dist = min(dist,i-index2)
else:
dist = min(dist,i-index1)
last_word = word1
index1 = i
#这里用elif则不会同一个词进两个条件
elif word == word2:
if last_word and last_word==word1:
dist = min(dist,i-index1)
last_word = word2
index2 = i
return dist
Explain
这个题解的思路是用两个指针index1和index2分别记录word1和word2最后出现的位置。遍历单词列表words，如果当前单词等于word1或word2，就更新对应指针，并计算当前位置与另一个单词最后出现位置的距离，更新最小距离dist。注意处理word1和word2相同的情况，若当前word等于word1且上一个词last_word等于word2，或者当前word等于word2且上一个词等于word1，都要更新最小距离。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def shortestWordDistance(self, words: List[str], word1: str, word2: str) -> int:
#和243一样，注意两个词一样的情况
if not words:
return None
index1,index2 = -1,-1 # 初始化指针，记录word1和word2的位置
last_word = None # 记录上一个出现的单词
dist = len(words)+1 # 初始化最小距离为一个大数
for i,word in enumerate(words): # 遍历单词列表
#word1==word2的情况都在这里处理
if word == word1:
if (last_word and last_word==word2) or (last_word and word1==word2): # 处理相邻单词的情况
if word1!=word2:
dist = min(dist,i-index2) # 更新最小距离
else:
dist = min(dist,i-index1) # 更新最小距离
last_word = word1 # 记录当前单词
index1 = i # 更新word1指针
#这里用elif则不会同一个词进两个条件
elif word == word2:
if last_word and last_word==word1: # 处理相邻单词的情况
dist = min(dist,i-index1) # 更新最小距离
last_word = word2 # 记录当前单词
index2 = i # 更新word2指针
return dist
Explore
在代码中，如果word1和word2相同，会特别处理这种情况。当遇到与word1相同的单词时，会更新index1的值，并且使用last_word变量检查前一个单词是否也是word1。如果是，这意味着相同的单词连续出现，此时会计算两次出现之间的距离，并更新最小距离dist。这种方法确保了即使word1和word2相同，代码也能正确处理连续出现的情况，实时更新最短距离。
在此代码实现中，`last_word`用于记录当前单词的前一个单词，主要用于判断两个连续单词是否是我们要比较的两个单词。这种方法可能导致误判的情况出现在：如果单词列表中存在多个连续的word1（或word2），而word1和word2是相同的，此时last_word会被连续更新为相同的值，导致无法适当地更新dist。例如，如果word1和word2相同，且连续出现多次，last_word会连续记录相同值，可能在某些情况下不正确地更新距离。
将最小距离`dist`初始化为`len(words)+1`是因为在单词列表中，两个单词的最大可能距离就是列表的长度（例如，一个单词在列表的开始，另一个在结束），因此初始化为列表长度加一是确保在开始比较之前，任何有效的距离都会小于这个初始值，从而获得正确的最小距离。此外，使用`len(words)+1`避免了引入特殊库或复杂的数据类型，如无限大（infinity），使得代码更简单、更容易理解。
当`word1`和`word2`是相同的单词时，算法的逻辑确保只有一个分支（`if`块）会被执行，此时`elif`块将不会执行。虽然这不会影响算法的正确性，因为适当的处理逻辑已经包含在`if`块中，但可能对效率有轻微影响。特别是在word1和word2相同且连续出现的情况下，每次遇到相同单词都需要进行比较和更新操作，这可能稍微增加执行时间。然而，这种影响通常是微小的，因为额外的处理仍然是必要的，以确保在相同单词连续出现时能够正确地计算最短距离。