dynamic_programming.regex_match
===============================

.. py:module:: dynamic_programming.regex_match

.. autoapi-nested-parse::

   Regex matching check if a text matches pattern or not.
   Pattern:

       1. ``.`` Matches any single character.
       2. ``*`` Matches zero or more of the preceding element.

   More info:
       https://medium.com/trick-the-interviwer/regular-expression-matching-9972eb74c03



Functions
---------

.. autoapisummary::

   dynamic_programming.regex_match.dp_match
   dynamic_programming.regex_match.recursive_match


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

.. py:function:: dp_match(text: str, pattern: str) -> bool

   Dynamic programming matching algorithm.

   | Time complexity: O(\|text\| * \|pattern\|)
   | Space complexity: O(\|text\| * \|pattern\|)

   :param text: Text to match.
   :param pattern: Pattern to match.
   :return: ``True`` if `text` matches `pattern`, ``False`` otherwise.

   >>> dp_match('abc', 'a.c')
   True
   >>> dp_match('abc', 'af*.c')
   True
   >>> dp_match('abc', 'a.c*')
   True
   >>> dp_match('abc', 'a.c*d')
   False
   >>> dp_match('aa', '.*')
   True


.. py:function:: recursive_match(text: str, pattern: str) -> bool

   Recursive matching algorithm.

   | Time complexity: O(2^(\|text\| + \|pattern\|))
   | Space complexity: Recursion depth is O(\|text\| + \|pattern\|).

   :param text: Text to match.
   :param pattern: Pattern to match.
   :return: ``True`` if `text` matches `pattern`, ``False`` otherwise.

   >>> recursive_match('abc', 'a.c')
   True
   >>> recursive_match('abc', 'af*.c')
   True
   >>> recursive_match('abc', 'a.c*')
   True
   >>> recursive_match('abc', 'a.c*d')
   False
   >>> recursive_match('aa', '.*')
   True