backtracking.word_ladder
========================

.. py:module:: backtracking.word_ladder

.. autoapi-nested-parse::

   Word Ladder is a classic problem in computer science.
   The problem is to transform a start word into an end word
   by changing one letter at a time.
   Each intermediate word must be a valid word from a given list of words.
   The goal is to find a transformation sequence
   from the start word to the end word.

   Wikipedia: https://en.wikipedia.org/wiki/Word_ladder



Functions
---------

.. autoapisummary::

   backtracking.word_ladder.backtrack
   backtracking.word_ladder.word_ladder


Module Contents
---------------

.. py:function:: backtrack(current_word: str, path: list[str], end_word: str, word_set: set[str]) -> list[str]

   Helper function to perform backtracking to find the transformation
   from the current_word to the end_word.

   Parameters:
   current_word (str): The current word in the transformation sequence.
   path (list[str]): The list of transformations from begin_word to current_word.
   end_word (str): The target word for transformation.
   word_set (set[str]): The set of valid words for transformation.

   Returns:
   list[str]: The list of transformations from begin_word to end_word.
              Returns an empty list if there is no valid
               transformation from current_word to end_word.

   Example:
   >>> backtrack("hit", ["hit"], "cog", {"hot", "dot", "dog", "lot", "log", "cog"})
   ['hit', 'hot', 'dot', 'lot', 'log', 'cog']

   >>> backtrack("hit", ["hit"], "cog", {"hot", "dot", "dog", "lot", "log"})
   []

   >>> backtrack("lead", ["lead"], "gold", {"load", "goad", "gold", "lead", "lord"})
   ['lead', 'lead', 'load', 'goad', 'gold']

   >>> backtrack("game", ["game"], "code", {"came", "cage", "code", "cade", "gave"})
   ['game', 'came', 'cade', 'code']


.. py:function:: word_ladder(begin_word: str, end_word: str, word_set: set[str]) -> list[str]

   Solve the Word Ladder problem using Backtracking and return
   the list of transformations from begin_word to end_word.

   Parameters:
   begin_word (str): The word from which the transformation starts.
   end_word (str): The target word for transformation.
   word_list (list[str]): The list of valid words for transformation.

   Returns:
   list[str]: The list of transformations from begin_word to end_word.
              Returns an empty list if there is no valid transformation.

   Example:
   >>> word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
   ['hit', 'hot', 'dot', 'lot', 'log', 'cog']

   >>> word_ladder("hit", "cog", ["hot", "dot", "dog", "lot", "log"])
   []

   >>> word_ladder("lead", "gold", ["load", "goad", "gold", "lead", "lord"])
   ['lead', 'lead', 'load', 'goad', 'gold']

   >>> word_ladder("game", "code", ["came", "cage", "code", "cade", "gave"])
   ['game', 'came', 'cade', 'code']