Question

Formatted question description: https://leetcode.ca/all/244.html

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

Constraints:

1 <= wordsDict.length <= 3 * 10⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2
At most 5000 calls will be made to shortest.

Algorithm

Need to call the function to find the shortest word distance multiple times, then the solution to the previous problem [243 Shortest-Word-Distance] is very inefficient.

Use HashMap to create a mapping between each word and all its appearing positions, and then when looking for the shortest word distance, you only need to take out the word’s mapped position array in HashMap for pairwise comparison.

Code

import java.util.ArrayList;
import java.util.HashMap;

public class Shortest_Word_Distance_II {

    public class WordDistance {

        HashMap<String, ArrayList<Integer>> map; // @note: duplicated cases

        public WordDistance(String[] words) {

            map = new HashMap<String, ArrayList<Integer>>();

            for (int i = 0; i < words.length; i++) {
                if (map.containsKey(words[i])) {
                    map.get(words[i]).add(i);
                } else {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    list.add(i);
                    map.put(words[i], list);
                }
            }
        }

        public int shortest(String word1, String word2) {
            ArrayList<Integer> l1 = map.get(word1);
            ArrayList<Integer> l2 = map.get(word2);

            int result = Integer.MAX_VALUE;

            // better than 2 for-loop
            int p1 = 0;
            int p2 = 0;
            while (p1 < l1.size() && p2 < l2.size()) {
                int v1 = l1.isEmpty() ? Integer.MAX_VALUE : l1.get(p1);
                int v2 = l2.isEmpty() ? Integer.MAX_VALUE : l2.get(p2);
                result = Math.min(result, Math.abs(v1 - v2));

                if (v1 < v2) {
                    p1++;
                } else {
                    p2++;
                }
            }
//            for (int i1 : l1) {
//                for (int i2 : l2) {
//                    result = Math.min(result, Math.abs(i1 - i2));
//                }
//            }

            return result;
        }
    }
}

############

class WordDistance {
    private Map<String, List<Integer>> d = new HashMap<>();

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

    public int shortest(String word1, String word2) {
        List<Integer> a = d.get(word1), b = d.get(word2);
        int ans = 0x3f3f3f3f;
        int i = 0, j = 0;
        while (i < a.size() && j < b.size()) {
            ans = Math.min(ans, Math.abs(a.get(i) - b.get(j)));
            if (a.get(i) <= b.get(j)) {
                ++i;
            } else {
                ++j;
            }
        }
        return ans;
    }
}

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

// OJ: https://leetcode.com/problems/shortest-word-distance-ii/
// Time:
//     * WordDistance: O(N)
//     * shortest: O(N)
// Space: O(N)
class WordDistance {
private:
    unordered_map<string, vector<int>> m;
public:
    WordDistance(vector<string> words) {
        for (int i = 0; i < words.size(); ++i) {
            m[words[i]].push_back(i);
        }
    }
    int shortest(string word1, string word2) {
        auto &a = m[word1], &b = m[word2];
        int i = 0, j = 0, dist = INT_MAX;
        while (i < a.size() && j < b.size() && dist > 1) {
            dist = min(dist, abs(a[i] - b[j]));
            if (a[i] > b[j]) ++j;
            else ++i;
        }
        return dist;
    }
};

class WordDistance:
    def __init__(self, wordsDict: List[str]):
        self.d = defaultdict(list)
        for i, w in enumerate(wordsDict):
            self.d[w].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        a, b = self.d[word1], self.d[word2]
        ans = inf
        i = j = 0
        while i < len(a) and j < len(b):
            ans = min(ans, abs(a[i] - b[j]))
            if a[i] <= b[j]:
                i += 1
            else:
                j += 1
        return ans


# Your WordDistance object will be instantiated and called as such:
# obj = WordDistance(wordsDict)
# param_1 = obj.shortest(word1,word2)

############

class WordDistance(object):
  def __init__(self, words):
    """
    initialize your data structure here.
    :type words: List[str]
    """
    self.d = {}
    for i in range(0, len(words)):
      self.d[words[i]] = self.d.get(words[i], []) + [i]

  def shortest(self, word1, word2):
    """
    Adds a word into the data structure.
    :type word1: str
    :type word2: str
    :rtype: int
    """
    l1 = self.d[word1]
    l2 = self.d[word2]
    i = j = 0
    ans = float("inf")
    while i < len(l1) and j < len(l2):
      ans = min(ans, abs(l1[i] - l2[j]))
      if l1[i] > l2[j]:
        j += 1
      else:
        i += 1
    return ans

# Your WordDistance object will be instantiated and called as such:
# wordDistance = WordDistance(words)
# wordDistance.shortest("word1", "word2")
# wordDistance.shortest("anotherWord1", "anotherWord2")

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

func Constructor(wordsDict []string) WordDistance {
	d := map[string][]int{}
	for i, w := range wordsDict {
		d[w] = append(d[w], i)
	}
	return WordDistance{d}
}

func (this *WordDistance) Shortest(word1 string, word2 string) int {
	a, b := this.d[word1], this.d[word2]
	ans := 0x3f3f3f3f
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		ans = min(ans, abs(a[i]-b[j]))
		if a[i] <= b[j] {
			i++
		} else {
			j++
		}
	}
	return ans
}

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

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

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

244 - Shortest Word Distance II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions