backtracking.word_break
=======================

.. py:module:: backtracking.word_break

.. autoapi-nested-parse::

   Word Break Problem is a well-known problem in computer science.
   Given a string and a dictionary of words, the task is to determine if
   the string can be segmented into a sequence of one or more dictionary words.

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



Functions
---------

.. autoapisummary::

   backtracking.word_break.backtrack
   backtracking.word_break.word_break


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

.. py:function:: backtrack(input_string: str, word_dict: set[str], start: int) -> bool

   Helper function that uses backtracking to determine if a valid
   word segmentation is possible starting from index 'start'.

   Parameters:
   input_string (str): The input string to be segmented.
   word_dict (set[str]): A set of valid dictionary words.
   start (int): The starting index of the substring to be checked.

   Returns:
   bool: True if a valid segmentation is possible, otherwise False.

   Example:
   >>> backtrack("leetcode", {"leet", "code"}, 0)
   True

   >>> backtrack("applepenapple", {"apple", "pen"}, 0)
   True

   >>> backtrack("catsandog", {"cats", "dog", "sand", "and", "cat"}, 0)
   False


.. py:function:: word_break(input_string: str, word_dict: set[str]) -> bool

   Determines if the input string can be segmented into a sequence of
   valid dictionary words using backtracking.

   Parameters:
   input_string (str): The input string to segment.
   word_dict (set[str]): The set of valid words.

   Returns:
   bool: True if the string can be segmented into valid words, otherwise False.

   Example:
   >>> word_break("leetcode", {"leet", "code"})
   True

   >>> word_break("applepenapple", {"apple", "pen"})
   True

   >>> word_break("catsandog", {"cats", "dog", "sand", "and", "cat"})
   False