243. Shortest Word Distance

leetcode easy

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

Task

Дан массив строк

wordsDict

и две разные строки, которые уже существуют в массиве:

word1

word2

. Верните кратчайшее расстояние между этими двумя словами в списке.

Пример

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

Output: 3

C# solution

matched/original

public class Solution {
    public int ShortestDistance(string[] words, string word1, string word2) {
        int minDistance = words.Length;
        for (int i = 0; i < words.Length; i++) {
            if (words[i] == word1) {
                for (int j = 0; j < words.Length; j++) {
                    if (words[j] == word2) {
                        minDistance = Math.Min(minDistance, Math.Abs(i - j));
                    }
                }
            }
        }
        return minDistance;
    }
}

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 ShortestDistance(vector<string> words, string word1, string word2) {
        int minDistance = words.size();
        for (int i = 0; i < words.size(); i++) {
            if (words[i] == word1) {
                for (int j = 0; j < words.size(); j++) {
                    if (words[j] == word2) {
                        minDistance = min(minDistance, abs(i - j));
                    }
                }
            }
        }
        return minDistance;
    }
}

Java solution

matched/original

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int minDistance = words.length;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                for (int j = 0; j < words.length; j++) {
                    if (words[j].equals(word2)) {
                        minDistance = Math.min(minDistance, Math.abs(i - j));
                    }
                }
            }
        }
        return minDistance;
    }
}

JavaScript solution

matched/original

class Solution {
    shortestDistance(words, word1, word2) {
        let minDistance = words.length;
        for (let i = 0; i < words.length; i++) {
            if (words[i] === word1) {
                for (let j = 0; j < words.length; j++) {
                    if (words[j] === word2) {
                        minDistance = Math.min(minDistance, Math.abs(i - j));
                    }
                }
            }
        }
        return minDistance;
    }
}

Python solution

matched/original

class Solution:
    def shortestDistance(self, words, word1, word2):
        minDistance = len(words)
        for i in range(len(words)):
            if words[i] == word1:
                for j in range(len(words)):
                    if words[j] == word2:
                        minDistance = min(minDistance, abs(i - j))
        return minDistance

Go solution

matched/original

type Solution struct{}

func (s *Solution) ShortestDistance(words []string, word1 string, word2 string) int {
    minDistance := len(words)
    for i, w1 := range words {
        if w1 == word1 {
            for j, w2 := range words {
                if w2 == word2 {
                    if diff := abs(i - j); diff < minDistance {
                        minDistance = diff
                    }
                }
            }
        }
    }
    return minDistance
}

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

Explanation

Algorithm

1️⃣

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

2️⃣

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

3️⃣

Сохраняйте минимальное найденное расстояние между двумя словами и возвращайте его в качестве результата.

😎