dynamic_programming.regex_match

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

‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.

More info:

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

Functions

dp_match(→ bool)	Dynamic programming matching algorithm.
recursive_match(→ bool)	Recursive matching algorithm.

Module Contents

dynamic_programming.regex_match.dp_match(text: str, pattern: str) → bool

Dynamic programming matching algorithm.

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

Parameters:

• text – Text to match.

• pattern – Pattern to match.

Returns:

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

dynamic_programming.regex_match.recursive_match(text: str, pattern: str) → bool

Recursive matching algorithm.

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

Parameters:

• text – Text to match.

• pattern – Pattern to match.

Returns:

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