Implement 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). The function prototype should be: bool is_match(const char *s, const char *p) Some examples: is_match("aa","a") → false is_match("aa","aa") → true is_match("aaa","aa") → false is_match("aa", "a*") → true is_match("aa", ".*") → true is_match("ab", ".*") → true is_match("aab", "c*a*b") → true """ def is_match(str_a, str_b): """Finds if `str_a` matches `str_b` Keyword arguments: str_a -- string str_b -- string """ len_a, len_b = len(str_a) + 1, len(str_b) + 1 matches = [[False] * len_b for _ in range(len_a)] # Match empty string with empty pattern matches[0][0] = True # Match empty string with .* for i, element in enumerate(str_b[1:], 2): matches[0][i] = matches[0][i - 2] and element == '*' for i, char_a in enumerate(str_a, 1): for j, char_b in enumerate(str_b, 1): if char_b != '*': # The previous character has matched and the current one # has to be matched. Two possible matches: the same or . matches[i][j] = matches[i - 1][j - 1] and \ char_b in (char_a, '.') else: # Horizontal look up [j - 2]. # Not use the character before *.. Complete.
Q8.
Implement 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).
The function prototype should be:
bool is_match(const char *s, const char *p)
Some examples:
is_match("aa","a") → false
is_match("aa","aa") → true
is_match("aaa","aa") → false
is_match("aa", "a*") → true
is_match("aa", ".*") → true
is_match("ab", ".*") → true
is_match("aab", "c*a*b") → true
"""
def is_match(str_a, str_b):
"""Finds if `str_a` matches `str_b`
Keyword arguments:
str_a -- string
str_b -- string
"""
len_a, len_b = len(str_a) + 1, len(str_b) + 1
matches = [[False] * len_b for _ in range(len_a)]
# Match empty string with empty pattern
matches[0][0] = True
# Match empty string with .*
for i, element in enumerate(str_b[1:], 2):
matches[0][i] = matches[0][i - 2] and element == '*'
for i, char_a in enumerate(str_a, 1):
for j, char_b in enumerate(str_b, 1):
if char_b != '*':
# The previous character has matched and the current one
# has to be matched. Two possible matches: the same or .
matches[i][j] = matches[i - 1][j - 1] and \
char_b in (char_a, '.')
else:
# Horizontal look up [j - 2].
# Not use the character before *..
Complete.
Step by step
Solved in 4 steps with 3 images
