Any suggestions on how to improve performance?


  • 0
    M

    I have ruby code written here but it fails due to Time Limit, is there anyway to improve this code? Thanks!

    # @param {String} begin_word
    # @param {String} end_word
    # @param {String[]} word_list
    # @return {String[][]}
    
    class Node
        attr_accessor :val, :parent
        def initialize(val, parent=nil)
            @val = val
            @parent = parent
        end
    end
    
    def find_ladders(begin_word, end_word, word_list)
        node, nodes = Node.new(begin_word), []
        travel(node, end_word, word_list, nodes)
        parse(nodes, end_word)    
    end
    
    def parse(nodes, end_word)
        return [] if nodes == []
    
        nodes.map do |n|
            seq = []
            while(n != nil)
                seq = [n.val] + seq
                n = n.parent
            end
            seq
        end.group_by{|s| s.size}.min.last    
    end
    
    def travel(node, end_word, word_list, nodes)
        return if word_list == []
        words = next_words(node.val, word_list) 
        words.each do |w| 
            child_node = Node.new(w, node)
            if w == end_word
                nodes << child_node
                return
            end
            travel(child_node, end_word, word_list - [w], nodes)
        end 
    end
    
    def next_words(word, word_list)
        word_list.select do |w|
            diff, la, lb = 0, w.split(""), word.split("")
            la.each_with_index do |a, i|
                diff += 1 if la[i] != lb[i]
            end
            
            diff == 1
        end
    end
    
    

Log in to reply
 

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