245. Shortest Word Distance II

leetcode medium

#array#csharp#graph#leetcode#math#medium#search#string

Task

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.

Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример

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

Output: 1

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int ShortestWordDistance(string[] wordsDict, string word1, string word2) {
        List<int> indices1 = new List<int>();
        List<int> indices2 = new List<int>();
        for (int i = 0; i < wordsDict.Length; i++) {
            if (wordsDict[i] == word1) {
                indices1.Add(i);
            }
            if (wordsDict[i] == word2) {
                indices2.Add(i);
            }
        }
        int shortestDistance = int.MaxValue;
        foreach (int index in indices1) {
            int x = indices2.BinarySearch(index);
            if (x < 0) {
                x = ~x;
            }
            if (x < indices2.Count) {
                shortestDistance = Math.Min(shortestDistance, indices2[x] - index);
            }
            if (x > 0 && indices2[x - 1] != index) {
                shortestDistance = Math.Min(shortestDistance, index - indices2[x - 1]);
            }
        }
        return shortestDistance;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ShortestWordDistance(vector<string> wordsDict, string word1, string word2) {
        List<int> indices1 = new List<int>();
        List<int> indices2 = new List<int>();
        for (int i = 0; i < wordsDict.size(); i++) {
            if (wordsDict[i] == word1) {
                indices1.push_back(i);
            }
            if (wordsDict[i] == word2) {
                indices2.push_back(i);
            }
        }
        int shortestDistance = int.MaxValue;
        foreach (int index in indices1) {
            int x = indices2.BinarySearch(index);
            if (x < 0) {
                x = ~x;
            }
            if (x < indices2.size()) {
                shortestDistance = min(shortestDistance, indices2[x] - index);
            }
            if (x > 0 && indices2[x - 1] != index) {
                shortestDistance = min(shortestDistance, index - indices2[x - 1]);
            }
        }
        return shortestDistance;
    }
}

Java solution

matched/original

import java.util.*;

class Solution {
    public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
        List<Integer> indices1 = new ArrayList<>();
        List<Integer> indices2 = new ArrayList<>();
        for (int i = 0; i < wordsDict.length; i++) {
            if (wordsDict[i].equals(word1)) {
                indices1.add(i);
            }
            if (wordsDict[i].equals(word2)) {
                indices2.add(i);
            }
        }

        int shortestDistance = Integer.MAX_VALUE;
        for (int index : indices1) {
            int x = Collections.binarySearch(indices2, index);
            if (x < 0) {
                x = -x - 1;
            }
            if (x < indices2.size()) {
                shortestDistance = Math.min(shortestDistance, indices2.get(x) - index);
            }
            if (x > 0 && !indices2.get(x - 1).equals(index)) {
                shortestDistance = Math.min(shortestDistance, index - indices2.get(x - 1));
            }
        }
        return shortestDistance;
    }
}

JavaScript solution

matched/original

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;
    }
}

Python solution

matched/original

from bisect import bisect_right

class Solution:
    def shortestWordDistance(self, wordsDict, word1, word2):
        indices1 = [i for i, word in enumerate(wordsDict) if word == word1]
        indices2 = [i for i, word in enumerate(wordsDict) if word == word2]
        
        shortestDistance = float('inf')
        for index in indices1:
            x = bisect_right(indices2, index)
            if x < len(indices2):
                shortestDistance = min(shortestDistance, indices2[x] - index)
            if x > 0 and indices2[x - 1] != index:
                shortestDistance = min(shortestDistance, index - indices2[x - 1])
        return shortestDistance

Go solution

matched/original

package main

import (
    "math"
    "sort"
)

func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
    var indices1, indices2 []int
    for i, word := range wordsDict {
        if word == word1 {
            indices1 = append(indices1, i)
        }
        if word == word2 {
            indices2 = append(indices2, i)
        }
    }

    shortestDistance := math.MaxInt32
    for _, index := range indices1 {
        x := sort.Search(len(indices2), func(i int) bool { return indices2[i] > index })
        if x < len(indices2) {
            shortestDistance = min(shortestDistance, indices2[x]-index)
        }
        if x > 0 && indices2[x-1] != index {
            shortestDistance = min(shortestDistance, index-indices2[x-1])
        }
    }
    return shortestDistance
}

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

Explanation

Algorithm

1️⃣

Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2️⃣

Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3️⃣

Верните значение переменной shortestDistance.

😎