https://leetcode.com/problems/word-search-ii/

212.rb

# @param {Character[][]} board
# @param {String[]} words
# @return {String[]}
def find_words(board, words)
  root = Node.new
  words.each do |w|
    root.add_word(w)
  end

  b = Board.new(board)
  found = []
  (0...b.height).each do |y|
    (0...b.width).each do |x|
      search(b, x, y, root, found)
    end
  end

  found
end

def search(board, x, y, node, found)
  char = board.at(x, y)
  return false if char.nil?

  child = node.child(char)
  return false if child.nil?

  if child.found?
    found << child.word
    node.root.delete_word(child.word)
    child.found!
  end

  board.set(x, y, nil)
  search(board, x, y - 1, child, found)
  search(board, x, y + 1, child, found)
  search(board, x - 1, y, child, found)
  search(board, x + 1, y, child, found)
  board.set(x, y, char)
end

class Board
  def initialize(board)
    @board = board
  end

  def width
    @width ||= @board[0].size
  end

  def height
    @height ||= @board.size
  end

  def valid_pos?(x, y)
    x >= 0 && x < width && y >= 0 && y < height
  end

  def at(x, y)
    if valid_pos?(x, y)
      @board[y][x]
    else
      nil
    end
  end

  def set(x, y, ch)
    @board[y][x] = ch
  end
end

class Node
  attr_reader :word

  def initialize(parent = nil)
    @parent = parent
  end

  def add_word(word, idx = 0)
    if word.size == idx
      @word = word
      return
    end

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

  def delete_word(word, idx = 0)
    return if word.size == idx

    ch = word[idx]
    child = children[ch]
    child.delete_word(word, idx + 1)
    if child.children.empty?
      children.delete(ch)
    end
  end

  def child(char)
    children[char]
  end

  def found?
    !!@word
  end

  def found!
    @word = nil
  end

  def children
    @children ||= {}
  end

  def root
    if @parent.nil?
      self
    else
      @parent.root
    end
  end
end