LeetCode 243. Shortest Word Distance

Description

https://leetcode.com/problems/shortest-word-distance/

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:

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

Example 2:

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

Constraints:

• 1 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] consists of lowercase English letters.
• word1 and word2 are in wordsDict.
• word1 != word2

Explanation

Compare the distance between word1 and word2 indices.

Python Solution

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        min_distance = sys.maxsize
        
        word1_indices = [] 
        word2_indices = []
        
        for i, word in enumerate(wordsDict):
            if word == word1:
                word1_indices.append(i)
            elif word == word2:
                word2_indices.append(i)
                
        
        for w1 in word1_indices:
            for w2 in word2_indices:
                min_distance = min(min_distance, abs(w2 - w1))
        
        
        return min_distance