
Problem Statement
The task requires finding the shortest distance between two specified words in a given list of words, wordsDict
. The words for comparison, word1
and word2
, are guaranteed to be present in the list. The "shortest distance" refers to the minimum number of indices that separate the two words in the array. It is important to consider that word1
and word2
might refer to the same word, adding a layer of complexity since one has to find the minimum distance between two occurrences of the same word if they are identical. The problem focuses on efficiently identifying and calculating this minimum distance while navigating through the nuances of potential word repetition and different words.
Examples
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
andword2
are inwordsDict
.
Approach and Intuition
This task can be tackled efficiently by iterating through the list wordsDict
and using a few variables to keep track of the positions of the words and the shortest distance found.
- Initialize two variables,
index1
andindex2
, to record the last seen indices ofword1
andword2
respectively. Both are initialized to some dummy values indicating they haven't been encountered yet. - Create a variable
min_distance
initialized to a large number that will store the shortest distance found during the iteration. - As you iterate through
wordsDict
, check for the occurrences ofword1
andword2
. - If
word1
is encountered, updateindex1
. Ifword2
is also encountered (either as a separate word or the same asword1
), updateindex2
. - After updating indices, if both
index1
andindex2
are valid (i.e., they have been updated at least once from their initial dummy values), compute the distance between the two indices. - If the computed distance is smaller than
min_distance
, updatemin_distance
. - Continue this process until the end of the list. The value in
min_distance
at the end of the iteration will be the shortest distance betweenword1
andword2
.
This method efficiently computes the shortest distance with just one pass through the list, making it optimal considering the constraints provided.
Solutions
- C++
class Solution {
public:
int findMinDistance(vector<string>& dictionary, string w1, string w2) {
int minDist = INT_MAX;
int lastIndex = -1;
for (int idx = 0; idx < dictionary.size(); idx++) {
if (dictionary[idx] == w1 || dictionary[idx] == w2) {
if (lastIndex != -1 && (dictionary[lastIndex] != dictionary[idx] || w1 == w2)) {
minDist = min(minDist, idx - lastIndex);
}
lastIndex = idx;
}
}
return minDist;
}
};
This C++ solution aims to address the problem of finding the shortest distance between two words in an array, which may be the same word (hence considering occurrences of a single word). The implementation is straightforward, focusing on minimizing iterations and effectively utilizing storage to track indices.
- The function
findMinDistance
receives avector<string> dictionary
containing the words, and twostring
variables,w1
andw2
, representing the words for which the distance needs to be calculated. - An integer
minDist
is initialized toINT_MAX
to keep track of the minimum distance found during the iteration. - Another integer
lastIndex
is initialized to-1
and serves as a marker to store the index of the previous occurrence of eitherw1
orw2
. - The function then iterates over the dictionary with a for loop. For each word at the current index (
idx
):- If the current word matches
w1
orw2
, the algorithm checks if a previous index (lastIndex
) was recorded and whether the word atlastIndex
is different from the current one, or it is the same (in scenarios wherew1
equalsw2
). - If the conditions hold true, it updates
minDist
to the minimum value between the storedminDist
and the difference betweenidx
andlastIndex
. lastIndex
is then set to the currentidx
.
- If the current word matches
- Finally, the function returns
minDist
, representing the shortest distance between the occurrences ofw1
andw2
.
This approach ensures that the solution is efficient with a time complexity of O(n), where n is the length of the dictionary, as it processes each word sequentially and performs minimal operations per word. The space complexity is O(1) since it only uses a few additional variables regardless of the input size.
- Java
class Solution {
public int findMinDistance(String[] wordsArray, String firstWord, String secondWord) {
int minDistance = Integer.MAX_VALUE;
int lastIndex = -1;
for (int index = 0; index < wordsArray.length; index++) {
if (wordsArray[index].equals(firstWord) || wordsArray[index].equals(secondWord)) {
if (lastIndex != -1 && (!wordsArray[lastIndex].equals(wordsArray[index]) || firstWord.equals(secondWord))) {
minDistance = Math.min(minDistance, index - lastIndex);
}
lastIndex = index;
}
}
return minDistance;
}
}
The Java solution provided aims to find the minimum distance between two given words in an array of words, where the same word can also be queried for its closest repeat. The function findMinDistance
accepts an array of strings (wordsArray
), and two strings (firstWord
and secondWord
) representing the words for which the distance is to be calculated.
Here’s a breakdown of how the logic is implemented:
- Initialize
minDistance
withInteger.MAX_VALUE
to track the smallest distance found. - Use
lastIndex
initialized to-1
to store the index of the last found target word. - Iterate through the
wordsArray
usingindex
. - Check if the current word is either
firstWord
orsecondWord
. - If
lastIndex
is not-1
and either the last word is not the same as the current word (i.e., searching for the distance between different words) or when both target words are the same (i.e., finding the shortest distance between repeats of the same word), updateminDistance
with the smaller value between the previously recordedminDistance
and the difference betweenindex
andlastIndex
. - Update
lastIndex
to the currentindex
. - After looping through the array, return
minDistance
.
This simple yet effective approach handles cases where both target words are the same or different, efficiently determining the shortest distance in a single pass through the array, making it optimal for scenarios where the word list is large or dynamic.
No comments yet.