Python short solution 92ms using dict


  • 5
    A
    class WordDistance:
        def __init__(self, words):
            self.dic = {}
            for index, w in enumerate(words):
                self.dic[w] = self.dic.get(w, []) + [index]
    
        def shortest(self, word1, word2):
            return min(abs(i1 - i2) for i1 in self.dic[word1] for i2 in self.dic[word2])

  • 0
    C

    The solution is not bad while the time complexity of shortest( ) function here is O(m*n), you can refer to this solution (https://leetcode.com/discuss/50185/java-solution-using-minimum-difference-between-sorted-arrays), where the time complexity is O(m+n).


  • 0
    A

    Thank you, that solution is much smarter than mine.


  • 0
    A

    Modified shortest() method to O(m + n) as caikehe mentioned in the comment, But the running time becomes bigger, about 110~130ms.

    class WordDistance:
        def __init__(self, words):
            self.dic = {}
            for index, w in enumerate(words):
                self.dic[w] = self.dic.get(w, []) + [index]
    
        def shortest(self, word1, word2):
            i1,i2,distance = 0,0,sys.maxint
            while i1 < len(self.dic[word1]) and i2 < len(self.dic[word2]):
                distance = min(distance, abs(self.dic[word1][i1]-self.dic[word2][i2]))
                # Move the smaller one forward
                if self.dic[word1][i1] > self.dic[word2][i2]:
                    i2 += 1
                else:
                    i1 += 1
            return distance
    

  • 0
    R

    Yes. I think this is due to for loops run faster than while loops in Python. And Leetcode's test case are relatively small so the run time complexity doesn't compensate the gap.


  • 0

    @aimee9098 said in Python short solution 92ms using dict:

    self.dic[w] = self.dic.get(w, []) + [index]

    self.dic[w] = self.dic.get(w, []) + [index]
    Is there anyone can help me explain this?


  • 0
    D

    hmm, i have a ruby version of this and it runs into time complexity issues.


Log in to reply
 

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