Time limit exceeded


  • 0
    K

    Using a BFS approach, I am facing a TLE at OJ for the input. Please suggest how I could improve the performance of the below code to pass the test case.

    "cet", "ism",["kid","tag","pup","ail",....]

    class Solution:
        # @param start, a string
        # @param end, a string
        # @param dict, a set of string
        # @return an integer
        def ladderLength(self,start, end, dict):
    
            queue = [start]
            used_word = []
            min_value = 1000000
            value = 0
            while queue:
                current_word = queue.pop()
                if self.EditDist(current_word, end) == 1:
                    min_value = min(min_value,value)
                for word in dict:
                    if self.EditDist(current_word, word) == 1 and word not in used_word:
                        value += 1
                        used_word.append(current_word)
                        queue.append(word)
            if min_value == 1000000:
                return 0
            return min_value
    
        def EditDist(self,word1,word2):
            length = len(word1)
            dist = 0
            for i in range(length):
                if word1[i] != word2[i]:
                    dist += 1
            return dist

Log in to reply
 

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