243. Shortest Word Distance

EasyArrayString
Leetcode Link

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 and j, to -1, to represent the most recent positions of word1 and word2, 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 index k and the current word w.
  • If w matches word1, update the position i to the current index k.
  • If w matches word2, update the position j to the current index k.
  • After each word match, if both i and j have been updated from their initial value of -1 (meaning both word1 and word2 have been found at least once), calculate the current distance between word1 and word2 using abs(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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

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:

  1. Initialize indices and answer variable:

    • Two index variables i and j are initialized to -1, which will keep track of the most recent positions of word1 and word2, respectively.
    • The variable ans is initialized to inf (infinity), which will be used to keep the smallest distance encountered.

  2. Iterate over array: The code uses a loop to iterate through each element of wordsDict with enumeration, which provides both index k and value w for every iteration.

  3. Find and update positions: During iteration, if the current word w equals word1, index i is updated to the current index k. Similarly, if w equals word2, index j is updated to the current index k.

  4. Calculate distance when both words are found: After any update to i or j, the solution checks if both i and j are not -1 anymore, indicating that both word1 and word2 have been encountered. At this point, it calculates the distance using the absolute difference abs(i - j).

  5. 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.

  6. Return the answer: After the loop ends, ans will contain the shortest distance between word1 and word2, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Example 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".

  1. Initialize indices and answer variable: i = -1, j = -1, ans = inf. i and j will hold the positions of "coding" and "practice" respectively once they are found, and ans will keep track of the shortest distance.

  2. Iterate over array:

    • At index k = 0, w = "practice". It matches word2, so we update j = 0.
    • At index k = 1, w = "makes". This doesn't match either word1 or word2.
    • At index k = 2, w = "perfect". This also doesn't match either word1 or word2.
    • At index k = 3, w = "coding". It matches word1, so we update i = 3.

  3. Calculate distance when both words are found:

    • Now we have found both word1 and word2 (i and j are not -1). So we compute the distance: abs(i - j) = abs(3 - 0) = 3.

  4. Update the shortest distance:

    • We compare 3 with ans which is inf. Since 3 is less, we update ans = 3.

  5. There are no more elements to process, so the loop ends.

  6. Return the answer:

    • At this point ans = 3, which is the shortest distance between "coding" and "practice" in the given wordsDict.

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
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫