LeetCode 244 Shortest Word Distance II

LeetCode

<div>

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:

<pre>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 </pre>

Constraints:

• 1 <= wordsDict.length <= 3 * 10<sup>4</sup>
• 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.

</div>

题目大意：

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

解题思路：

记录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为两单词下标列表的最短长度