244. Shortest Word Distance II

using System;
using System.Collections.Generic;
public class WordDistance {
    private Dictionary<string, List<int>> locations;
    public WordDistance(string[] words) {
        locations = new Dictionary<string, List<int>>();
        for (int i = 0; i < words.Length; i++) {
            if (!locations.ContainsKey(words[i])) {
                locations[words[i]] = new List<int>();
            }
            locations[words[i]].Add(i);
        }
    }
    public int Shortest(string word1, string word2) {
        List<int> loc1 = locations[word1];
        List<int> loc2 = locations[word2];
        int l1 = 0, l2 = 0, minDiff = int.MaxValue;
        while (l1 < loc1.Count && l2 < loc2.Count) {
            minDiff = Math.Min(minDiff, Math.Abs(loc1[l1] - loc2[l2]));
            if (loc1[l1] < loc2[l2]) {
                l1++;
            } else {
                l2++;
            }
        }
        return minDiff;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class WordDistance {
    private unordered_map<string, List<int>> locations;
    public WordDistance(vector<string> words) {
        locations = new unordered_map<string, List<int>>();
        for (int i = 0; i < words.size(); i++) {
            if (!locations.count(words[i])) {
                locations[words[i]] = new List<int>();
            }
            locations[words[i]].push_back(i);
        }
    }
    public int Shortest(string word1, string word2) {
        List<int> loc1 = locations[word1];
        List<int> loc2 = locations[word2];
        int l1 = 0, l2 = 0, minDiff = int.MaxValue;
        while (l1 < loc1.size() && l2 < loc2.size()) {
            minDiff = min(minDiff, abs(loc1[l1] - loc2[l2]));
            if (loc1[l1] < loc2[l2]) {
                l1++;
            } else {
                l2++;
            }
        }
        return minDiff;
    }
}

import java.util.*;

class WordDistance {
    Map<String, List<Integer>> locations;

    public WordDistance(String[] words) {
        locations = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            locations.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> loc1 = locations.get(word1);
        List<Integer> loc2 = locations.get(word2);
        int l1 = 0, l2 = 0, minDiff = Integer.MAX_VALUE;

        while (l1 < loc1.size() && l2 < loc2.size()) {
            minDiff = Math.min(minDiff, Math.abs(loc1.get(l1) - loc2.get(l2)));
            if (loc1.get(l1) < loc2.get(l2)) {
                l1++;
            } else {
                l2++;
            }
        }
        return minDiff;
    }
}

class WordDistance {
    constructor(words) {
        this.locations = new Map();
        words.forEach((word, i) => {
            if (!this.locations.has(word)) {
                this.locations.set(word, []);
            }
            this.locations.get(word).push(i);
        });
    }

    shortest(word1, word2) {
        const loc1 = this.locations.get(word1);
        const loc2 = this.locations.get(word2);
        let l1 = 0, l2 = 0, minDiff = Infinity;

        while (l1 < loc1.length && l2 < loc2.length) {
            minDiff = Math.min(minDiff, Math.abs(loc1[l1] - loc2[l2]));
            if (loc1[l1] < loc2[l2]) {
                l1++;
            } else {
                l2++;
            }
        }
        return minDiff;
    }
}

class WordDistance:

    def __init__(self, words):
        self.locations = {}
        for i, word in enumerate(words):
            if word not in self.locations:
                self.locations[word] = []
            self.locations[word].append(i)

    def shortest(self, word1, word2):
        loc1 = self.locations[word1]
        loc2 = self.locations[word2]
        l1, l2 = 0, 0
        min_diff = float('inf')
        while l1 < len(loc1) and l2 < len(loc2):
            min_diff = min(min_diff, abs(loc1[l1] - loc2[l2]))
            if loc1[l1] < loc2[l2]:
                l1 += 1
            else:
                l2 += 1
        return min_diff

package main

import (
    "math"
)

type WordDistance struct {
    locations map[string][]int
}

func Constructor(words []string) WordDistance {
    locations := make(map[string][]int)
    for i, word := range words {
        locations[word] = append(locations[word], i)
    }
    return WordDistance{locations: locations}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
    loc1 := this.locations[word1]
    loc2 := this.locations[word2]
    l1, l2 := 0, 0
    minDiff := math.MaxInt32

    for l1 < len(loc1) && l2 < len(loc2) {
        minDiff = min(minDiff, abs(loc1[l1]-loc2[l2]))
        if loc1[l1] < loc2[l2] {
            l1++
        } else {
            l2++
        }
    }
    return minDiff
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Explanation

Algorithm

1️⃣

В конструкторе класса переберите заданный список слов и создайте словарь, сопоставляя слово с его позициями в массиве. Поскольку мы обрабатываем слова слева направо, индексы будут по умолчанию отсортированы для всех слов.

2️⃣

Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3️⃣

Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎