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<sup>4</sup>*1 <= wordsDict[i].length <= 10*wordsDict[i]consists of lowercase English letters. *word1andword2are inwordsDict. *word1 != word2`

题目大意：

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

解题思路：

同向双指针，扫一遍。贪婪法，肯定相邻，所以扫一遍

解题步骤：

N/A

注意事项：

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

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)

算法思路II：

同向双指针，取出每个单词的所有下标L1, L2,双指针比较，类似于merge sort的merge