strings.wildcard_pattern_matching¶

Implementation of regular expression matching with support for ‘.’ and ‘*’. ‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Attributes¶

input_string

Functions¶

match_pattern(→ bool)

uses bottom-up dynamic programming solution for matching the input

Module Contents¶

strings.wildcard_pattern_matching.match_pattern(input_string: str, pattern: str) → bool¶

uses bottom-up dynamic programming solution for matching the input string with a given pattern.

Runtime: O(len(input_string)*len(pattern))

Arguments¶

input_string: str, any string which should be compared with the pattern pattern: str, the string that represents a pattern and may contain ‘.’ for single character matches and ‘*’ for zero or more of preceding character matches

Note¶

the pattern cannot start with a ‘*’, because there should be at least one character before *

Returns¶

A Boolean denoting whether the given string follows the pattern

Examples¶

>>> match_pattern("aab", "c*a*b")
True
>>> match_pattern("dabc", "*abc")
False
>>> match_pattern("aaa", "aa")
False
>>> match_pattern("aaa", "a.a")
True
>>> match_pattern("aaab", "aa*")
False
>>> match_pattern("aaab", ".*")
True
>>> match_pattern("a", "bbbb")
False
>>> match_pattern("", "bbbb")
False
>>> match_pattern("a", "")
False
>>> match_pattern("", "")
True

strings.wildcard_pattern_matching.input_string = 'aab'¶