LeetCode 243 Shortest Word Distance

LeetCode

Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

Example 1:

Input: wordsDict = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1 = “coding”, word2 = “practice”
Output: 3

Example 2:

Input: wordsDict = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1 = “makes”, word2 = “coding”
Output: 1

Constraints:

`1 <= wordsDict.length <= 3 10⁴*1 <= wordsDict[i].length <= 10*wordsDict[i]

consists of lowercase English letters.
*

word1andword2are inwordsDict

.
*

word1 != word2`

题目大意：

求单词列表中给定的两个单词的最短下标距离

解题思路：

同向双指针

解题步骤：

N/A

注意事项：

同向双指针，分别指向两单词，计算结果时必须是找到才比较

Python代码：

def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
	p1 = p2 = -1
	res = float('inf')
	for i, word in enumerate(wordsDict):
		if word == word1:
			p1 = i
		if word == word2:
			p2 = i
		if p1 != -1 and p2 != -1:
			res = min(res, abs(p1 - p2))
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)