Shortest Word Distance II

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 241 ms)

Metric	Value
Runtime	241 ms
Memory	53.7 MB
Date	2022-01-28

Solution

public class WordDistance {

    Dictionary<string, List<int>> indices;

    public WordDistance(string[] wordsDict)
    {
        indices = new Dictionary<string, List<int>>();
        for (int i = 0; i < wordsDict.Length; i++)
        {
            if(indices.ContainsKey(wordsDict[i]))
            {
                indices[wordsDict[i]].Add(i);
            }
            else
            {
                indices.Add(wordsDict[i], new List<int>() {i});
            }
        }
    }

    public int Shortest(string word1, string word2)
    {

        List<int> ind1 = indices[word1]; List<int> ind2 = indices[word2];
        int min = Int32.MaxValue;
        for (int i = 0, j=0; i < ind1.Count && j< ind2.Count; )
        {
            min = Math.Min(Math.Abs(ind1[i]- ind2[j]), min);
            if(ind1[i]< ind2[j])
            {
                i++;
            }
            else j++;
        }

        return min;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(wordsDict);
 * int param_1 = obj.Shortest(word1,word2);
 */

📜 1 more C# submission(s)

Submission (2022-01-28) — 305 ms, 53.6 MB

public class WordDistance {

    private string[] wordsDict;
    Dictionary<(string,string), int> cache;
    Dictionary<string, List<int>> indices;

    public WordDistance(string[] wordsDict)
    {
        this.wordsDict = wordsDict;
        cache = new Dictionary<(string, string), int>();
        indices = new Dictionary<string, List<int>>();
        for (int i = 0; i < wordsDict.Length; i++)
        {
            if(indices.ContainsKey(wordsDict[i]))
            {
                indices[wordsDict[i]].Add(i);
            }
            else
            {
                indices.Add(wordsDict[i], new List<int>() {i});
            }
        }
    }

    public int Shortest(string word1, string word2)
    {
        if(cache.ContainsKey((word1, word2)))
        return cache[(word1, word2)];
        if (cache.ContainsKey((word2, word1)))
        return cache[(word2, word1)];
        
        List<int> ind1 = indices[word1]; List<int> ind2 = indices[word2];
        int min = Int32.MaxValue;
        for (int i = 0, j=0; i < ind1.Count && j< ind2.Count; )
        {
            min = Math.Min(Math.Abs(ind1[i]- ind2[j]), min);
            if(ind1[i]< ind2[j])
            {
                i++;
            }
            else j++;
        }
        
        cache.Add((word1, word2), min);
        cache.Add((word2, word1), min);
        return min;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(wordsDict);
 * int param_1 = obj.Shortest(word1,word2);
 */

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed