Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Shortest Word Distance (easy)

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!
T

Thai Minh

· 3 years ago

class Solution:
  def shortestDistance(self, words, word1, word2):
    # TODO: Write your code here
    # Find index of word1 and word 2 in words array
    # when we update the indexes reupdate the min distance between index1 and index2
    index1, index2 = -1, -1
    curr_min = len(words)
    for i, word in enumerate(words):
      if word == word1:
        index1 = i
      if word == word2:
        index2 = i
      if index1 != -1 and index2 != -1: 
        curr_min = min(curr_min, abs(index1 - index2))
    return curr_min
Show 1 reply
L

Luke

· 3 years ago

Any suggestions for further practice on this type of problem?

Sachin Dev S

Sachin Dev S

· 2 years ago

How to solve if the words can be same and we want to find the distance between them.

Manoj Tiwari

Manoj Tiwari

· a year ago

Why am I not able to uncheck "mark as done" and also do we have any space to write notes!!

T

tignatova001

· 10 months ago

In the contsraints they have: words[i] consists of lowercase English letters.

So I tried to catch that error, but the test case actually CAN contain alphanumeric, as one of the tests are "word1", "word2"

wasim ahmed

wasim ahmed

· 5 months ago

class Solution:
  def shortestDistance(self, words, word1, word2):
    # TODO: Write your code here
    word_map = {}
    n = len(words)
    for i in range(n):
      if words[i] == word1 or words[i] == word2:
        word_map[words[i]] = word_map.get(words[i], []) + [i]
    
    word_map[word1] = sorted(word_map[word1])
    word_map[word2] = sorted(word_map[word2])
    mn = n
    print()
    for i in word_map[word1]:
      for j in word_map[word2]:
        mn = min(mn, abs(i-j))
    return mn