Does word ladder support ruby? I always get TLE for this question.


  • 0
    J

    Here is my code. Really don't how to optimize it...

    For the TLE example, it costs around 267 millisecond locally.

    Here is my code:

    def self.ladder_length(from, to, dict)
        return unless dict.is_a? Set
    
        queue = [from]
        level_queue = [1]
        dict.delete(from) # Modify original dict will save time, but it will ruin it.
    
        until queue.empty?
          word = queue.shift
          l = level_queue.shift
          (0..word.size-1).each do |i|
            ('a'..'z').each do |c|
              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
        end
        0
      end

  • 1

    A better algorithm would be good, but I also got yours accepted after some optimizations:

    def self.ladder_length(from, to, dict)
        return unless dict.is_a? Set
    
        queue = [from]
        level_queue = [1]
        dict.delete(from) # Modify original dict will save time, but it will ruin it.
        letters = 'a'..'z'
        dict << to
        
        until queue.empty?
          word = queue.shift
          l = level_queue.shift
          indexes = 0...word.size
          letters.each do |c|
            indexes.each do |i|
                word_copy = word.dup
                word_copy[i] = c
                if dict.include?(word_copy)
                  return l + 1 if word_copy == to
                  queue << word_copy
                  level_queue << l + 1
                  dict.delete(word_copy)
                end
            end
          end
        end
        0
      end

  • 0
    J

    Hmm... You Rock Stefan!!! With this implementation, the TLE example reduces to 195 millisecond locally.


Log in to reply
 

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