Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Shortest Word Distance

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

.....

.....

.....

Like the course? Get enrolled and start learning!
I

izanmubarak

· 3 years ago

I'm not really seeing how this is a two pointer solution. It seems like you only loop through the array from start to finish to store the positions of the two words with a single pointer, and you update shortestDistance accordingly

Show 1 reply
Bruno Ely

Bruno Ely

· 3 years ago

String comparison is not a constant-time operation, so the loop that runs O(N) times is doing O(K) work every time. This matters because you could have a list of words in the order of tens or hundreds of words, but words in the order of thousands of characters since it wasn't specified that "words" must actually be English words and can't be full books, for instance.

Show 2 replies
Sachin Dev S

Sachin Dev S

· 2 years ago

 and use two pointers to track the positions of these words.

this should be two variable and not "two pointer", it's confusion with 2 pointer pattern

Show 1 reply
Manuel

Manuel

· 2 years ago

This part of the code will be called multiple times unnecessarily

// If both the positions are updated, update the shortest distance
if (position1 != -1 && position2 != -1) {
    shortestDistance = Math.min(shortestDistance, Math.abs(position1 - position2));
}

Scenario:

String[] words = { "a", "c", "d", "b","x" ,"a" };
String word1 = "a";
String word2 = "b";
Dmitry Gachkovsky

Dmitry Gachkovsky

· 3 years ago

Because to me it's not intuitive why by jumping with the pointers to any found instances of word1or word2 we guaranteed to handle all the cases and get the shortest distance

Show 1 reply
A

anuraagkiran555

· 2 years ago

Correct me if I'm wrong but consider this scenario.

["a", "c", "d", "b", "a", "f", "g", "h", "b"]

shortest distance would be returned as 4 instead of 1

Show 1 reply
Joshua Ferguson

Joshua Ferguson

· 3 months ago

this can also be solved recursively. few notes:

start with distance 1 and update on tail call. If you hit the end, just return a max val. exit early if match is found while distance is 1 otherwise distance is min of current distance and find_next with word1,word2 swapped

ps. generators are lazy in python, so next will exit after first match

import sys
class Solution:
  def shortestDistance(self, words, word1, word2):
    def find_next(current: str, other: str, idx: int=0, distance: int=1):
      if idx==len(words):
        return sys.maxsize
      if words[idx]==other:
        return distance if distance==1 else min(distance, find_next(other, current, idx+1))
      elif words[idx]==current:
        return find_next(current,other,idx+1)
      return find_next(current,other