列表

详情

244. 最短单词距离 II

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

实现 WordDistanc 类:

 

示例 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

 

注意:

相似题目

合并两个有序链表

最短单词距离

最短单词距离 III

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class WordDistance { public: WordDistance(vector<string>& wordsDict) { } int shortest(string word1, string word2) { } }; /** * Your WordDistance object will be instantiated and called as such: * WordDistance* obj = new WordDistance(wordsDict); * int param_1 = obj->shortest(word1,word2); */

golang 解法, 执行用时: 24 ms, 内存消耗: 8.5 MB, 提交时间: 2023-10-22 10:38:43 

type WordDistance map[string][]int

func Constructor(wordsDict []string) WordDistance {
    indicesMap := WordDistance{}
    for i, word := range wordsDict {
        indicesMap[word] = append(indicesMap[word], i)
    }
    return indicesMap
}

func (indicesMap WordDistance) Shortest(word1, word2 string) int {
    ans := math.MaxInt32
    indices1 := indicesMap[word1]
    indices2 := indicesMap[word2]
    i, n := 0, len(indices1)
    j, m := 0, len(indices2)
    for i < n && j < m {
        index1, index2 := indices1[i], indices2[j]
        ans = min(ans, abs(index1-index2))
        if index1 < index2 {
            i++
        } else {
            j++
        }
    }
    return ans
}

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

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


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

java 解法, 执行用时: 26 ms, 内存消耗: 48.7 MB, 提交时间: 2023-10-22 10:38:29 

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

    public WordDistance(String[] wordsDict) {
        int length = wordsDict.length;
        for (int i = 0; i < length; i++) {
            String word = wordsDict[i];
            indicesMap.putIfAbsent(word, new ArrayList<Integer>());
            indicesMap.get(word).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> indices1 = indicesMap.get(word1);
        List<Integer> indices2 = indicesMap.get(word2);
        int size1 = indices1.size(), size2 = indices2.size();
        int pos1 = 0, pos2 = 0;
        int ans = Integer.MAX_VALUE;
        while (pos1 < size1 && pos2 < size2) {
            int index1 = indices1.get(pos1), index2 = indices2.get(pos2);
            ans = Math.min(ans, Math.abs(index1 - index2));
            if (index1 < index2) {
                pos1++;
            } else {
                pos2++;
            }
        }
        return ans;
    }
}


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

cpp 解法, 执行用时: 36 ms, 内存消耗: 19.7 MB, 提交时间: 2023-10-22 10:38:14 

class WordDistance {
public:
    WordDistance(vector<string>& wordsDict) {
        int length = wordsDict.size();
        for (int i = 0; i < length; i++) {
            string word = wordsDict[i];
            indicesMap[word].emplace_back(i);
        }
    }
    
    int shortest(string word1, string word2) {
        vector<int> indices1 = indicesMap[word1];
        vector<int> indices2 = indicesMap[word2];
        int size1 = indices1.size(), size2 = indices2.size();
        int pos1 = 0, pos2 = 0;
        int ans = INT_MAX;
        while (pos1 < size1 && pos2 < size2) {
            int index1 = indices1[pos1], index2 = indices2[pos2];
            ans = min(ans, abs(index1 - index2));
            if (index1 < index2) {
                pos1++;
            } else {
                pos2++;
            }
        }
        return ans;
    }
private:
    unordered_map<string, vector<int>> indicesMap;
};


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

python3 解法, 执行用时: 64 ms, 内存消耗: 24.2 MB, 提交时间: 2023-10-22 10:37:48 

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

    def shortest(self, word1: str, word2: str) -> int:
        ans = inf
        indices1 = self.indicesMap[word1]
        indices2 = self.indicesMap[word2]
        i, n = 0, len(indices1)
        j, m = 0, len(indices2)
        while i < n and j < m:
            index1, index2 = indices1[i], indices2[j]
            ans = min(ans, abs(index1 - index2))
            if index1 < index2:
                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)

上一题

© 2024 leetcode.cn