243. Shortest Word Distance

LeetCode 243. Shortest Word Distance

Description

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 * 104

• 1 <= wordsDict[i].length <= 10

• wordsDict[i] consists of lowercase English letters.

• word1 and word2 are in wordsDict.

• word1 != word2

Tags

Array

Solution

Use 2 pointers p1 and p2, starting from both the first appearances respectively, to record every index of word1 and word2. If the current word is word1, p1 will move to the index of the current one; so will p2. After moving, update the smallest distance with abs(p1 - p2). Finally, we return that smallest distance.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

func shortestDistance(wordsDict []string, word1 string, word2 string) int {
	ans, p1, p2 := 1<<31, -1, -1
	for i, w := range wordsDict {
		if w == word1 {
			p1 = i
		} else if w == word2 {
			p2 = i
		}
		if p1 != -1 && p2 != -1 {
			if n := abs(p1 - p2); n < ans {
				ans = n
			}
		}
	}
	return ans
}

func abs(a int) int {
	if a < 0 {
		return -1 * a
	}
	return a
}

Reference

1. 最短单词距离