https://leetcode.com/problems/prefix-and-suffix-search/

745.rb

class WordFilter
  def initialize(words)
    @root = Node.new
    words.each.with_index do |w, weight|
      (0..w.size).each do |len|
        s = "#{w[-len, len]}@#{w}"
        @root.add_word(weight, s, 0)
      end
    end
  end

  def f(prefix, suffix)
    query = "#{suffix}@#{prefix}"
    node = @root.find(query, 0)
    node&.weight || -1
  end

  class Node
    attr_reader :weight

    def initialize
      @weight = -1
    end

    def add_word(weight, word, idx)
      @weight = [@weight, weight].max
      return if word.size == idx

      ch = word[idx]
      child = children[ch]
      unless child
        child = Node.new
        children[ch] = child
      end
      child.add_word(weight, word, idx + 1)
    end

    def find(prefix, idx)
      return self if prefix.size == idx

      ch = prefix[idx]
      child = children[ch]
      child&.find(prefix, idx + 1)
    end

    def children
      @children ||= {}
    end
  end
end