Ruby solution using a combination of DFS and Trie (with test output)


  • 0
    T

    set @test = true to see the output.

    Runs through preparation steps to get the orders, then builds the trie, adjusting the branches along the way.

    # @param {String[]} words
    # @return {String}
    def alien_order(words)
      word_tree = build_word_tree(words)
      return "" unless word_tree
      order = get_orders(word_tree)
      @test = false
      root = Node.new(nil)
      nodes = {}
      order.each do |word|
        puts "\nword is #{word}" if @test
        buffer_keys = {}
        buffer_root = nil
        buffer_leaf = nil
        (0...word.length).each do |i|
          puts "tree: " + stringify(root).to_s if @test
          puts "nodes: " + nodes.map {|k,v| k}.join(',') if @test
          a, b = word[i], word[i + 1]
          next if a == b
          if b && nodes[a] && nodes[b]
            return "" unless update(nodes[a], nodes[b])
            next
          elsif b && nodes[a]
            puts "sees a #{a}, but not a #{b}" if @test
            new_node = Node.new(b)
            nodes[b] = new_node
            nodes[a].children[b] = new_node
            new_node.parent = nodes[a]
            next
          end
          next if nodes[a] && i == word.length - 1
          return "" if buffer_keys[a]
          puts "building a buffer for #{a}, current_buffer: #{stringify(buffer_root)}" if @test
          buffer_keys[a] = true
          node = Node.new(a)
          nodes[a] = node
          buffer_root ||= node
          buffer_leaf.children[node.val] = node if buffer_leaf
          node.parent = buffer_leaf if buffer_leaf
          buffer_leaf = node
          if nodes[b]
            start = nodes[b].parent
            finish = nodes[b]
            squeeze(start, buffer_root, buffer_leaf, finish)
            next
          elsif i >= word.length - 1
            root.children[buffer_root.val] = buffer_root
            buffer_root.parent = root
            break
          end
        end
      end
      stringify(root).to_s
    end
    
    def build_word_tree(words)
      root = Node.new(nil)
      words.each do |word|
        node = root
        old_node = false
        word.each_char do |c|
          if node.children[c]
            last = node.children.map {|k,v| k}.last
            return false if last != c
            node = node.children[c]
            old_node = true
          else
            old_node = false
            new_node = Node.new(c)
            node.children[c] = new_node
            node = new_node
          end
        end
        if old_node && node.children.length > 0
          puts "an old node with children: #{node.val}: #{node.children.map{|k,v| k}}"
          return false
        end
      end
      return root
    end
    
    def get_orders(word_tree)
      sets = []
      queue = [word_tree]
      while queue.length > 0
        node = queue.pop
        sets << node.children.map {|k,v| k}
        queue += node.children.map {|k,v| v}
      end
      sets
    end
    
    def stringify(root)
      word = ""
      return word if root.nil?
      depth = 0
      queue = [root]
      while queue.length > 0
        depth += 1
        new_queue = []
        queue.each do |node|
          word += "#{depth}#{node.val}" if node.val && @test
          word += node.val if node.val && !@test
          new_queue += node.children.map {|k,v| v}
        end
        queue = new_queue
    
      end
      word
    end
    
    def squeeze(start, buffer_root, buffer_leaf, finish)
      start.children.delete(finish.val)
      start.children[buffer_root.val] = buffer_root
      buffer_root.parent = start
      buffer_leaf.children[finish.val] = finish
      finish.parent = buffer_leaf
    end
    
    def update(node1, node2)
      puts "updating #{node1.val}->#{node2.val}" if @test
      node = node2
      while node
        break if node == node1
        node = node.parent
      end
      return true if node
    
      node = node1
    
      while node
        break if node == node2
        node = node.parent
      end
      return false unless node.nil?
      node2.parent.children.delete(node2.val)
      node1.children[node2.val] = node2
      node2.parent = node1
    end
    
    
    class Node
      attr_accessor :children, :parent, :val
      def initialize(val)
        @val = val
        @children = {}
      end
    end
    

Log in to reply
 

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