[LeetCode] 244. Shortest Word Distance II 最短单词距离 II

This is afollow upofShortest Word Distance. The only difference is now you are given the list of words and your method will be calledrepeatedlymany times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two wordsword1andword2and return the shortest distance between these two words in the list.

For example,
Assume that words =["practice", "makes", "perfect", "coding", "makes"].

Givenword1=“coding”,word2=“practice”, return 3.
Givenword1="makes",word2="coding", return 1.

Note:
You may assume thatword1does not equal toword2, andword1andword2are both in the list.

243. Shortest Word Distance的拓展，不同的是这次需要多次调用求最短单词距离的函数。

Python:

# Time:  init: O(n), lookup: O(a + b), a, b is occurences of word1, word2
# Space: O(n)
import collections

class WordDistance:
    # initialize your data structure here.
    # @param {string[]} words
    def __init__(self, words):
        self.wordIndex = collections.defaultdict(list)
        for i in xrange(len(words)):
            self.wordIndex[words[i]].append(i)

    # @param {string} word1
    # @param {string} word2
    # @return {integer}
    # Adds a word into the data structure.
    def shortest(self, word1, word2):
        indexes1 = self.wordIndex[word1]
        indexes2 = self.wordIndex[word2]

        i, j, dist = 0, 0, float("inf")
        while i < len(indexes1) and j < len(indexes2):
            dist = min(dist, abs(indexes1[i] - indexes2[j]))
            if indexes1[i] < indexes2[j]:
                i += 1
            else:
                j += 1

        return dist

更多相关文章

随机推荐