Python O(n) time and O(n) space beating 92% - Works for both Shortest word distance I and II


  • 0
    K

    """class WordDistance(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.dict = {}
        for index, word in enumerate(words):
            if self.dict.has_key(word):
                self.dict[word].append(index)
            else:
                self.dict[word] = [index]
        
                
    
    def shortest(self, word1, word2):
        word1_indices = self.dict[word1]
        word2_indices = self.dict[word2]
        word1_index_len = len(word1_indices)
        word2_index_len = len(word2_indices)
        min_Diff = float("inf")
        i = 0
        j = 0
        while i < word1_index_len and j < word2_index_len:
            current_diff = abs(word1_indices[i] - word2_indices[j])
            if current_diff < min_Diff:
                min_Diff = abs(current_diff)
            if word1_indices[i] > word2_indices[j]:
                j+=1
            else:
                i+=1
        return min_Diff"""
       WordDistance object will be instantiated and called as such:
    

    obj = WordDistance(words)

    param_1 = obj.shortest(word1,word2)'''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.