243. Shortest Word Distance
Problem Description
In this problem, you are given an array of strings called wordsDict
, which contains a list of words. You are also given two different strings word1
and word2
which you can be certain are present in wordsDict
. Your task is to find the shortest distance between word1
and word2
within wordsDict
. The distance between two words is the number of words between them in the list (or the absolute difference between their indices in wordsDict
). You need to consider the case where there may be multiple occurrences of word1
and/or word2
, and you should find the minimum distance among all possible pairs of word1
and word2
.
Intuition
To find the shortest distance between two words in an array, a straightforward approach is to scan through the array while keeping track of the positions of the two words. Here's the thinking process leading to the solution:
- Initialize two index pointers,
i
andj
, to -1, to represent the most recent positions ofword1
andword2
, respectively. - Initialize
ans
(answer) to infinity to keep track of the current minimum distance.inf
in the code stands for infinity, representing an initially large distance. - Iterate through
wordsDict
using a loop, keeping track of the indexk
and the current wordw
. - If
w
matchesword1
, update the positioni
to the current indexk
. - If
w
matchesword2
, update the positionj
to the current indexk
. - After each word match, if both
i
andj
have been updated from their initial value of -1 (meaning bothword1
andword2
have been found at least once), calculate the current distance betweenword1
andword2
usingabs(i - j)
. - Update
ans
with the smallest of its current value and the new distance just calculated. - After completing the loop, return
ans
.
By keeping track of the latest occurrences of the two words, we can efficiently calculate the distances between new occurrences and existing ones, ensuring we always have the shortest distance discovered during the iteration.
Solution Approach
The solution uses a one-pass algorithm to find the shortest distance between two words in an array. Here's how it's implemented:
-
Initialize indices and answer variable:
- Two index variables
i
andj
are initialized to-1
, which will keep track of the most recent positions ofword1
andword2
, respectively. - The variable
ans
is initialized toinf
(infinity), which will be used to keep the smallest distance encountered.
- Two index variables
-
Iterate over array: The code uses a loop to iterate through each element of
wordsDict
with enumeration, which provides both indexk
and valuew
for every iteration. -
Find and update positions: During iteration, if the current word
w
equalsword1
, indexi
is updated to the current indexk
. Similarly, ifw
equalsword2
, indexj
is updated to the current indexk
. -
Calculate distance when both words are found: After any update to
i
orj
, the solution checks if bothi
andj
are not-1
anymore, indicating that bothword1
andword2
have been encountered. At this point, it calculates the distance using the absolute differenceabs(i - j)
. -
Update the shortest distance: The calculated distance is then compared with
ans
. If it is smaller,ans
is updated with the new distance. This ensures that at the end of the loop,ans
holds the minimum distance between the two words. -
Return the answer: After the loop ends,
ans
will contain the shortest distance betweenword1
andword2
, which the function then returns.
This algorithm exhibits a linear time complexity, i.e., O(n), where n is the number of elements in wordsDict
, as it only requires a single pass through the list. No extra space is used, apart from a few variables for indices and the minimum distance, so the space complexity is O(1). The simplicity and efficiency of this method make it a good choice for this problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Letās walk through a small example to illustrate the solution approach.
Imagine our wordsDict
is ["practice", "makes", "perfect", "coding", "makes"]
, and we are tasked to find the shortest distance between word1 = "coding"
and word2 = "practice"
.
-
Initialize indices and answer variable:
i = -1
,j = -1
,ans = inf
.i
andj
will hold the positions of "coding" and "practice" respectively once they are found, andans
will keep track of the shortest distance. -
Iterate over array:
- At index
k = 0
,w = "practice"
. It matchesword2
, so we updatej = 0
. - At index
k = 1
,w = "makes"
. This doesn't match eitherword1
orword2
. - At index
k = 2
,w = "perfect"
. This also doesn't match eitherword1
orword2
. - At index
k = 3
,w = "coding"
. It matchesword1
, so we updatei = 3
.
- At index
-
Calculate distance when both words are found:
- Now we have found both
word1
andword2
(i
andj
are not -1). So we compute the distance:abs(i - j) = abs(3 - 0) = 3
.
- Now we have found both
-
Update the shortest distance:
- We compare
3
withans
which isinf
. Since3
is less, we updateans = 3
.
- We compare
-
There are no more elements to process, so the loop ends.
-
Return the answer:
- At this point
ans = 3
, which is the shortest distance between "coding" and "practice" in the givenwordsDict
.
- At this point
In conclusion, after walking through the example, the shortest distance between the two words "coding" and "practice" is 3, as they are three words apart from each other in the list. This demonstrates how the one-pass solution efficiently computes the shortest distance with simple updates to index variables while iterating through the list only once.
Solution Implementation
1from typing import List
2
3class Solution:
4 def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
5 # Initialize indices for the positions of word1 and word2
6 index1 = index2 = -1
7 # Initialize the answer as infinite to ensure any actual distance found is smaller
8 shortest_distance = float('inf')
9
10 # Loop through the words in the dictionary to find the closest distance
11 for index, word in enumerate(wordsDict):
12 if word == word1:
13 index1 = index # Update the position of word1
14 if word == word2:
15 index2 = index # Update the position of word2
16
17 # If both words have been found at least once, calculate the distance
18 if index1 != -1 and index2 != -1:
19 distance = abs(index1 - index2) # Compute absolute difference
20 shortest_distance = min(shortest_distance, distance) # Update the shortest distance
21
22 # Return the shortest distance found between the two words
23 return shortest_distance
24
1class Solution {
2 // Method to find the shortest distance between two words in a dictionary
3 public int shortestDistance(String[] wordsDict, String word1, String word2) {
4 // Initialize the minimum distance to a very high value
5 int minDistance = Integer.MAX_VALUE;
6
7 // These will hold the last seen positions of word1 and word2
8 int lastPosWord1 = -1;
9 int lastPosWord2 = -1;
10
11 // Loop through the words dictionary to find the words
12 for (int index = 0; index < wordsDict.length; ++index) {
13 // If the current word equals word1, update lastPosWord1
14 if (wordsDict[index].equals(word1)) {
15 lastPosWord1 = index;
16 }
17 // If the current word equals word2, update lastPosWord2
18 if (wordsDict[index].equals(word2)) {
19 lastPosWord2 = index;
20 }
21 // If both last positions are set and not -1, calculate the distance
22 if (lastPosWord1 != -1 && lastPosWord2 != -1) {
23 // Update the minimum distance if a new minimum is found
24 minDistance = Math.min(minDistance, Math.abs(lastPosWord1 - lastPosWord2));
25 }
26 }
27 // Return the minimum distance found
28 return minDistance;
29 }
30}
31
1#include <vector>
2#include <string>
3#include <climits> // Include for INT_MAX
4
5class Solution {
6public:
7 // Function to find the shortest distance between two words in a list
8 int shortestDistance(std::vector<std::string>& wordsDict, std::string word1, std::string word2) {
9 int shortestDistance = INT_MAX; // Initialize shortest distance with the maximum possible value
10 // Use indices word1Index and word2Index to keep track of the most recent positions of word1 and word2
11 // Initialize both indices to -1, indicating that these words have not been encountered yet
12 int word1Index = -1;
13 int word2Index = -1;
14
15 // Loop through all words in the dictionary
16 for (int k = 0; k < wordsDict.size(); ++k) {
17 if (wordsDict[k] == word1) { // If the current word is word1
18 word1Index = k; // Update index of word1
19 }
20 if (wordsDict[k] == word2) { // If the current word is word2
21 word2Index = k; // Update index of word2
22 }
23
24 // If both words have been seen at least once
25 if (word1Index != -1 && word2Index != -1) {
26 // calculate the distance and update shortestDistance if it's smaller
27 shortestDistance = std::min(shortestDistance, std::abs(word1Index - word2Index));
28 }
29 }
30
31 // Return the shortest distance found
32 return shortestDistance;
33 }
34};
35
1// Importing necessary functionalities
2import { min, abs, MAX_VALUE } from 'math';
3
4// Function to find the shortest distance between two words in a list
5function shortestDistance(wordsDict: string[], word1: string, word2: string): number {
6 // Initialize shortest distance with the maximum possible value
7 let shortestDistance: number = MAX_VALUE;
8 // Use indices word1Index and word2Index to keep track of the most recent positions of word1 and word2
9 // Initialize both indices to -1, indicating that these words have not been encountered yet
10 let word1Index: number = -1;
11 let word2Index: number = -1;
12
13 // Loop through all words in the dictionary
14 for (let k = 0; k < wordsDict.length; ++k) {
15 if (wordsDict[k] === word1) { // If the current word is word1
16 word1Index = k; // Update index of word1
17 }
18 if (wordsDict[k] === word2) { // If the current word is word2
19 word2Index = k; // Update index of word2
20 }
21
22 // If both words have been seen at least once
23 if (word1Index !== -1 && word2Index !== -1) {
24 // Calculate the distance and update shortestDistance if it's smaller
25 shortestDistance = min(shortestDistance, abs(word1Index - word2Index));
26 }
27 }
28
29 // Return the shortest distance found
30 return shortestDistance;
31}
32
Time and Space Complexity
The time complexity of the code provided is O(n)
, where n
is the length of the wordsDict
list. This is because the code processes each word in the list exactly once in a single loop.
The space complexity of the code is O(1)
. It uses a fixed number of variables i
, j
, and ans
that do not depend on the size of the input list. Therefore, the amount of additional memory used does not increase with the size of wordsDict
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!