Ruby solution with Trie


  • 0
    T

    First creates a trie, then iterates through nodes using lazy comparison between trie nodes.

    # @param {String[]} words
    # @return {String[][]}
    
    
    def word_squares(words)
      @test = false
      @t = Trie.new
      @count = 0
      words.each do |w|
        @t.add_word(w)
      end
      n = words.first.length
      nodes = []
      @t.root.children.each do |k, node|
        node_set = match_count([node], n)
        if node_set.flatten.length > 0
          nodes += node_set
        end
      end
      return nodes.map {|n| n.flatten.map(&:value) }
    end
    
    def match_count(nodes, length) []
      return [nodes] if nodes.length >= length
      return_nodes = []
      node_set = nodes.map do |node|
        node.children.map {|k, n| n}
      end
      possible_nodes = comb_nodes(node_set)
      possible_nodes.each do |node_list|
        str = node_list.map {|v| v.value[-1] }.join
        node = @t.search(str)
        next if node.nil?
        node.children.each do |k, new_node|
          set = match_count(node_list + [new_node], length)
          return_nodes += set if set.length > 0
        end
      end
      return return_nodes
    end
    
    def comb_nodes(node_set)
      node_combinations = []
      node_set[0].each do |node|
        if node_set.length == 1
          node_combinations << [node]
        else
          node_combinations += comb_nodes(node_set[1..-1]).map do |nodes|
            nodes.unshift(node)
          end
        end
      end
      return node_combinations
    end
    
    class Trie
      attr_accessor :root
    
      def search(word)
        return nil if word.nil?
        node = @root
        word.each_char do |c|
          node = node.children[c]
          return nil if node.nil?
        end
    
        return node
      end
    
      def initialize
        @root = Node.new
      end
    
      def add_word(word)
        node = @root
        val = ""
        word.each_char do |c|
          val += c
          node.children[c] ||= Node.new
          node = node.children[c]
          node.value = val
        end
      end
    end
    
    class Node
      attr_accessor :value, :children
    
      def initialize
        @children = {}
      end
    
      def to_s
        puts "node: #{value}"
      end
    
    end
    

Log in to reply
 

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