LeetCode 244 Shortest Word Distance II

LeetCode

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.
*

word1andword2are inwordsDict

.
*

word1 != word2* At most5000calls will be made toshortest`.

题目大意：

设计数据结构返回单词列表中两单词下标最短距离。单词列表含重复单词

解题思路：

记录word到下标列表。可以用logn搜索另一个列表，总时间复杂度为O(nlogn)。不如用mergesort的merge来计算，复杂度为O(n)

解题步骤：

N/A

注意事项：

Python代码：

class WordDistance(TestCases):

    def __init__(self, wordsDict: List[str]):
        self.word_to_indices = collections.defaultdict(list)
        for i in range(len(wordsDict)):
            self.word_to_indices[wordsDict[i]].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        indices1 = self.word_to_indices[word1]
        indices2 = self.word_to_indices[word2]
        i, j, res = 0, 0, float('inf')
        while i < len(indices1) and j < len(indices2):
            res = min(res, abs(indices1[i] - indices2[j]))
            if indices1[i] <= indices2[j]:
                i += 1
            else:
                j += 1
        return res

算法分析：

shortest时间复杂度为O(L)，空间复杂度O(1)。L为两单词下标列表的最短长度