Problem description:

Given an array of strings wordsDict 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:

1
2
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3

Example 2:

1
2
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Solution:

Use two variable to track latest index of word1 and word2. When encounter different word and the we found the word before, update the res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def shortestDistance(self, words: List[str], word1: str, word2: str) -> int:
        res = len(words)
        position1, position2 = -1, -1
        for i in range(len(words)):
            if words[i] == word1:
                position1 = i
                if position2 != -1:
                    res = min(res, abs(position1 - position2))
            elif words[i] == word2:
                position2 = i
                if position1 != -1:
                    res = min(res, abs(position1 - position2))
        return res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: