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 uses bottomup dynamic programming solution for matching the input string with a given pattern runtime oleninputstringlenpattern arguments inputstring 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 matchpatternaab cab true matchpatterndabc abc false matchpatternaaa aa false matchpatternaaa a a true matchpatternaaab aa false matchpatternaaab true matchpatterna bbbb false matchpattern bbbb false matchpatterna false matchpattern true dp is a 2d matrix where dpij denotes whether prefix string of length i of inputstring matches with prefix string of length j of given pattern dp stands for dynamic programming since string of zero length match pattern of zero length since pattern of zero length will never match with string of nonzero length since string of zero length will match with pattern where there is at least one alternatively now using bottomup approach to find for all remaining lengths inputing the strings inputstring inputinput a string pattern inputinput a pattern using function to check whether given string matches the given pattern 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 dp is a 2d matrix where dp i j denotes whether prefix string of length i of input_string matches with prefix string of length j of given pattern dp stands for dynamic programming since string of zero length match pattern of zero length since pattern of zero length will never match with string of non zero length since string of zero length will match with pattern where there is at least one alternatively now using bottom up approach to find for all remaining lengths inputing the strings input_string input input a string pattern input input a pattern using function to check whether given string matches the given pattern
def match_pattern(input_string: str, pattern: str) -> bool:
    

    len_string = len(input_string) + 1
    len_pattern = len(pattern) + 1

    
    
    
    
    dp = [[0 for i in range(len_pattern)] for j in range(len_string)]

    
    dp[0][0] = 1

    
    for i in range(1, len_string):
        dp[i][0] = 0

    
    
    for j in range(1, len_pattern):
        dp[0][j] = dp[0][j - 2] if pattern[j - 1] == "*" else 0

    
    for i in range(1, len_string):
        for j in range(1, len_pattern):
            if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
                dp[i][j] = dp[i - 1][j - 1]

            elif pattern[j - 1] == "*":
                if dp[i][j - 2] == 1:
                    dp[i][j] = 1
                elif pattern[j - 2] in (input_string[i - 1], "."):
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = 0
            else:
                dp[i][j] = 0

    return bool(dp[-1][-1])


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    
    
    

    input_string = "aab"
    pattern = "c*a*b"

    
    if match_pattern(input_string, pattern):
        print(f"{input_string} matches the given pattern {pattern}")
    else:
        print(f"{input_string} does not match with the given pattern {pattern}")