Задача: 243. Shortest Word Distance
Сложность: easy

Дан массив строк и два слова. Нужно вернуть минимальное расстояние между ними в массиве.

Пример:

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

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

1⃣Проходим по массиву один раз, запоминая последние индексы, где встречались word1 и word2

2⃣При каждом новом вхождении одного из слов, если другое уже найдено — обновляем минимальное расстояние

3⃣Возвращаем минимальное расстояние

😎 Решение:

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int idx1 = -1, idx2 = -1, minDist = words.size();
        for (int i = 0; i < words.size(); ++i) {
            if (words[i] == word1) idx1 = i;
            else if (words[i] == word2) idx2 = i;
            if (idx1 != -1 && idx2 != -1) {
                minDist = min(minDist, abs(idx1 - idx2));
            }
        }
        return minDist;
    }
};

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