Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний