Given an array of strings wordsDict
and two strings that already exist in the array word1
and word2
, return the shortest distance between these two words in the list.
Note:
word1
and word2
may be the same.word1
and word2
are both in the list.Example 1:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1
Example 2:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3
Constraints:
1 <= wordsDict.length <= 105
1 <= wordsDict[i].length <= 10
wordsDict[i]
consists of lowercase English letters.word1
and word2
are in wordsDict
.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
We are given a list of words and two target words, which might be the same. The brute force approach involves checking every possible pair of locations of the target words to find the shortest distance between them.
Here's how the algorithm would work step-by-step:
def shortest_word_distance_iii_brute_force(words, word1, word2):
word1_locations = []
word2_locations = []
# Find all locations for the first word
for index, word in enumerate(words):
if word == word1:
word1_locations.append(index)
# Find all locations for the second word
for index, word in enumerate(words):
if word == word2:
word2_locations.append(index)
minimum_distance = float('inf')
# Need to check every possible pair of locations
for word1_location in word1_locations:
for word2_location in word2_locations:
# Handle the case where word1 and word2 are the same
if word1 == word2 and word1_location == word2_location:
continue
distance = abs(word1_location - word2_location)
minimum_distance = min(minimum_distance, distance)
return minimum_distance
This problem asks for the smallest distance between two specific words in a list of words. What makes it tricky is that the two words might be the same! We'll track the places where we find each word and be careful to avoid counting the distance from a word to itself when the target words are identical.
Here's how the algorithm would work step-by-step:
def shortestWordDistance(words, word1, word2):
word1_indices = []
word2_indices = []
for index, word in enumerate(words):
if word == word1:
word1_indices.append(index)
if word == word2:
word2_indices.append(index)
minimum_distance = float('inf')
# If the words are different, compare all pairs
if word1 != word2:
for i in word1_indices:
for j in word2_indices:
minimum_distance = min(minimum_distance, abs(i - j))
# If the words are the same, avoid comparing an index to itself
else:
for i in range(len(word1_indices)):
for j in range(len(word1_indices)):
if i != j:
minimum_distance = min(minimum_distance, abs(word1_indices[i] - word1_indices[j]))
return minimum_distance
Case | How to Handle |
---|---|
words is null or empty | Return Integer.MAX_VALUE, as no distance can be calculated. |
target is null or empty | Return Integer.MAX_VALUE, since no occurrences can be found. |
words array has only one element and that element is target | Return 0, as the shortest distance between the target word and itself is zero. |
target does not appear in words | Return Integer.MAX_VALUE, indicating no valid distance. |
words array contains only the target word | Return 0, as the distance between any two occurrences will be 0. |
Integer overflow when calculating the distance (large indices) | Use Math.abs() and ensure the distance is stored in a long to prevent overflow. |
Many occurrences of the target word, leading to many distance calculations | The iterative approach with two pointers efficiently handles a large number of target word occurrences. |
The only occurrences of the target are adjacent to each other | The min calculation correctly handles adjacent indices, resulting in a distance of 1. |