This problem asks to find the shortest distance between two given words within an array of strings. The optimal approach is a single pass through the array, tracking the indices of the target words.
The solution uses a single iteration through the wordsDict
array. We maintain two integer variables, i
and j
, to store the most recent indices of word1
and word2
respectively. Initially, both are set to -1, indicating that neither word has been encountered yet.
During each iteration:
word1
: If the current word (wordsDict[k]
) is equal to word1
, we update i
to the current index k
.word2
: Similarly, if the current word is equal to word2
, we update j
to k
.i
and j
are not -1 (meaning both words have been found at least once), we calculate the absolute difference between i
and j
(abs(i - j)
) and update the minimum distance (ans
) if this difference is smaller.After iterating through the entire array, ans
will hold the shortest distance between word1
and word2
.
wordsDict
. We perform a single pass through the array.i
, j
, ans
).The provided code snippets in Python, Java, C++, and Go all implement this approach effectively. They differ slightly in syntax and library functions used for absolute value calculation and minimum finding, but the core logic remains identical.
Example (Python):
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
i = j = -1
ans = float('inf') # Use infinity for initial minimum distance
for k, w in enumerate(wordsDict):
if w == word1:
i = k
if w == word2:
j = k
if i != -1 and j != -1:
ans = min(ans, abs(i - j))
return ans
The other languages utilize similar techniques: Java uses Integer.MAX_VALUE
as the initial maximum distance; C++ uses INT_MAX
; and Go defines a custom abs
function and uses math.MaxInt32
. The core algorithm remains consistent across all implementations.