Задача: 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 {
    function shortestWordDistance($wordsDict, $word1, $word2) {
        $indices1 = [];
        $indices2 = [];
        foreach ($wordsDict as $i => $word) {
            if ($word == $word1) {
                $indices1[] = $i;
            }
            if ($word == $word2) {
                $indices2[] = $i;
            }
        }

        $shortestDistance = PHP_INT_MAX;
        foreach ($indices1 as $index) {
            $x = $this->upper_bound($indices2, $index);
            if ($x < count($indices2)) {
                $shortestDistance = min($shortestDistance, $indices2[$x] - $index);
            }
            if ($x > 0 && $indices2[$x - 1] != $index) {
                $shortestDistance = min($shortestDistance, $index - $indices2[$x - 1]);
            }
        }
        return $shortestDistance;
    }

    function upper_bound($arr, $val) {
        $left = 0;
        $right = count($arr);
        while ($left < $right) {
            $mid = (int

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