Задача: 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.

😎 Решение:

class Solution {
    shortestWordDistance(wordsDict, word1, word2) {
        const indices1 = [];
        const indices2 = [];
        wordsDict.forEach((word, i) => {
            if (word === word1) {
                indices1.push(i);
            }
            if (word === word2) {
                indices2.push(i);
            }
        });

        let shortestDistance = Infinity;
        indices1.forEach(index => {
            const x = indices2.findIndex(i => i > index);
            if (x !== -1) {
                shortestDistance = Math.min(shortestDistance, indices2[x] - index);
            }
            if (x > 0 && indices2[x - 1] !== index) {
                shortestDistance = Math.min(shortestDistance, index - indices2[x - 1]);
            }
        });
        return shortestDistance;
    }
}

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