The reasons cause BFS TLE


  • 3
    D

    Two key parts in the BFS algorithms must be taken care of, otherwise it will lead to TLE:

    1. Instead of looping through the whole dict, change the testing word character by character will save a lot of time. This is a good trick;

    2. Maintaining a hashset to check visited words will result in TLE. Remove the visited nodes from dict will save some running time. I do not like this part. If you did not make a copy of the dict, the algorithm will change the original dict, which make me feel bad. If you made a copy, you did not save any space compare to using a hash set.


  • 0
    J

    I applied the above comments but still get TLE. Here is my code:

    def self.ladder_length(from, to, dict)
        queue = [from]
        level_queue = [1]
        dict.delete(from)
    
        until queue.empty?
          word = queue.shift
          l = level_queue.shift
          (0..word.size-1).each do |i|
            ('a'..'z').each do |c|
              next if word[i] == c
              word_copy = word.dup
              word_copy[i] = c
              return l + 1 if word_copy == to
              if dict.include?(word_copy)
                queue << word_copy
                level_queue << l + 1
                dict.delete(word_copy)
              end
            end
          end
        end
        0
      end

Log in to reply
 

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