Solution: Shortest Word Distance

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Shortest Word Distance

Table of Contents

Contents are not accessible

Problem Statement

Given an array of strings words and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.

Example 1:

Input: words = ["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"], word1 = "fox", word2 = "dog"
Output: 5
Explanation: The distance between "fox" and "dog" is 5 words.

Example 2:

Input: words = ["a", "c", "d", "b", "a"], word1 = "a", word2 = "b"
Output: 1
Explanation: The shortest distance between "a" and "b" is 1 word. Please note that "a" appeared twice.

Example 3:

Input: words = ["a", "b", "c", "d", "e"], word1 = "a", word2 = "e"
Output: 4
Explanation: The distance between "a" and "e" is 4 words.

Constraints:

2 <= words.length <= 3 * 10<sup>4</sup>
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
word1 and word2 are in words.
word1 != word2

Solution

To find the shortest distance between two given words, we can iterate through the list of words and use two pointers to track the positions of these words. Whenever we find one of these words in the list, we will update the word's position and calculate the distance from the other word. This way, we will keep track of the shortest distance between the two words.

Here's how the algorithm will work:

Initialize two variables position1 and position2 to store the positions of word1 and word2 in the words list, respectively. Initialize these variables to -1 which means that the words haven't been found yet.
Initialize a variable shortestDistance with the length of the words list as the initial value. This value will be updated later in the loop as the shortest distance is found.
Loop through the words list and for each word, check if it is word1 or word2. If it is word1, update position1 with the current index. If it is word2, update position2 with the current index.
If both position1 and position2 have been updated, that means both word1 and word2 have been found in the words list. In this case, update the shortestDistance with the absolute difference of the positions of word1 and word2.
Repeat steps 3 and 4 until the end of the words list is reached.
Return the final value of shortestDistance as the result.

Code

Here is the code for this algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

The algorithm iterates through the words array exactly once, using a single for loop. For each word, it performs constant-time operations: checking if the word matches either word1 or word2, and updating the positions.
The time complexity for this approach is $O(N)$ , where N is the number of words in the input array. This is because each word in the array is processed exactly once.

Space Complexity

The algorithm uses a few additional variables (position1, position2, and shortestDistance) that store integer values. These variables require constant space, $O(1)$ , since the space used does not scale with the size of the input.
No additional data structures or dynamic memory are used that depend on the size of the input.

Thus, the overall complexity is:

Time Complexity: $O(N)$
Space Complexity: $O(1)$

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible