README.md

244. 最短单词距离 II

English Version

题目描述

请设计一个类，使该类的构造函数能够接收一个字符串数组。然后再实现一个方法，该方法能够分别接收两个单词，并返回列表中这两个单词之间的最短距离。

实现 WordDistanc 类:

• WordDistance(String[] wordsDict) 用字符串数组 wordsDict 初始化对象。
• int shortest(String word1, String word2) 返回数组 worddict 中 word1 和 word2 之间的最短距离。

 

示例 1:

输入: 
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
输出:
[null, 3, 1]

解释：
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // 返回 3
wordDistance.shortest("makes", "coding");    // 返回 1

 

注意:

• 1 <= wordsDict.length <= 3 * 104
• 1 <= wordsDict[i].length <= 10
• wordsDict[i] 由小写英文字母组成
• word1 和 word2 在数组 wordsDict 中
• word1 != word2
•  shortest 操作次数不大于 5000 

解法

Python3

class WordDistance:

    def __init__(self, wordsDict: List[str]):
        self.words = {}
        for i, word in enumerate(wordsDict):
            indexes = self.words.get(word, [])
            indexes.append(i)
            self.words[word] = indexes

    def shortest(self, word1: str, word2: str) -> int:
        idx1, idx2 = self.words[word1], self.words[word2]
        i1 = i2 = 0
        shortest = float('inf')
        while i1 < len(idx1) and i2 < len(idx2):
            shortest = min(shortest, abs(idx1[i1] - idx2[i2]))
            smaller = idx1[i1] < idx2[i2]
            if smaller:
                i1 += 1
            else:
                i2 += 1
        return shortest


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

Java

class WordDistance {
    private Map<String, List<Integer>> words;

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

    public int shortest(String word1, String word2) {
        List<Integer> idx1 = words.get(word1);
        List<Integer> idx2 = words.get(word2);
        int i1 = 0, i2 = 0, shortest = Integer.MAX_VALUE;
        while (i1 < idx1.size() && i2 < idx2.size()) {
            shortest = Math.min(shortest, Math.abs(idx1.get(i1) - idx2.get(i2)));
            boolean smaller = idx1.get(i1) < idx2.get(i2);
            if (smaller) {
                ++i1;
            } else {
                ++i2;
            }
        }
        return shortest;
    }
}

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

...