This problem asks to find the shortest distance between two words (which could be the same word) in a list of strings. The solution employs a single pass through the input array wordsDict
, optimizing for efficiency.
Approach:
The solution efficiently handles two cases:
word1
and word2
are the same: We iterate through the array, keeping track of the most recent index of word1
. When we encounter another instance of word1
, we calculate the distance to the previously found instance and update the minimum distance (ans
).
word1
and word2
are different: We track the most recent indices of both word1
and word2
(i
and j
). Once we've found both words, we calculate the distance and update the minimum.
Time Complexity Analysis:
The solution iterates through the wordsDict
array exactly once. Therefore, the time complexity is O(n), where n is the length of wordsDict
.
Space Complexity Analysis:
The solution uses a constant amount of extra space to store variables like ans
, i
, and j
. Therefore, the space complexity is O(1).
Code Explanation (Python):
class Solution:
def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
ans = len(wordsDict) # Initialize with maximum possible distance
if word1 == word2: # Case 1: Same words
j = -1
for i, w in enumerate(wordsDict):
if w == word1:
if j != -1: # If a previous instance exists
ans = min(ans, i - j) #Update shortest distance
j = i #Update last seen index
else: # Case 2: Different words
i = j = -1
for k, w in enumerate(wordsDict):
if w == word1:
i = k
elif w == word2:
j = k
if i != -1 and j != -1: #Both words found
ans = min(ans, abs(i - j)) #Update shortest distance
return ans
The other language implementations (Java, C++, Go) follow the same logic, adapting syntax and data structures accordingly. They all achieve the same O(n) time and O(1) space complexity.
The min
function (or its equivalent in other languages) is used to track the shortest distance found so far. The abs
function (or equivalent) calculates the absolute difference between indices for the distance. The use of -1
as initial index values indicates that the word hasn't been encountered yet.