Задача: 245. Shortest Word Distance II
Сложность: medium

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.

Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример:

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

👨‍💻 Алгоритм:

1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3️⃣Верните значение переменной shortestDistance.

😎 Решение:

from bisect import bisect_right

class Solution:
    def shortestWordDistance(self, wordsDict, word1, word2):
        indices1 = [i for i, word in enumerate(wordsDict) if word == word1]
        indices2 = [i for i, word in enumerate(wordsDict) if word == word2]
        
        shortestDistance = float('inf')
        for index in indices1:
            x = bisect_right(indices2, index)
            if x < len(indices2):
                shortestDistance = min(shortestDistance, indices2[x] - index)
            if x > 0 and indices2[x - 1] != index:
                shortestDistance = min(shortestDistance, index - indices2[x - 1])
        return shortestDistance

Ставь 👍 и забирай 📚 Базу знаний