Задача: 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 {
    func shortestWordDistance(_ wordsDict: [String], _ word1: String, _ word2: String) -> Int {
        var indices1 = [Int]()
        var indices2 = [Int]()
        for (i, word) in wordsDict.enumerated() {
            if word == word1 {
                indices1.append(i)
            }
            if word == word2 {
                indices2.append(i)
            }
        }

        var shortestDistance = Int.max
        for index in indices1 {
            let x = indices2.partitioningIndex(where: { $0 > index })
            if x < indices2.count {
                shortestDistance = min(shortestDistance, indices2[x] - index)
            }
            if x > 0 && indices2[x - 1] != index {
                shortestDistance = min(shortestDistance, index - indices2[x - 1])
            }
        }
        return shortestDistance
    }
}

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