

"""simple docstring"""






def   lowercase_	(    _lowercase       :		List[str]							,      _lowercase       :		Optional[int]	):




					'''simple docstring'''






					UpperCAmelCase			:   List[str]      =				len(UpperCamelCase__	) + 1
					UpperCAmelCase			:   Any      =				len(UpperCamelCase__	) + 1

					# 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.
					UpperCAmelCase			:   Dict      =				[[0 for i in range(UpperCamelCase__	)] for j in range(UpperCamelCase__	)]

					# since string of zero length match pattern of zero length
					UpperCAmelCase			:   str      =				1

					# since pattern of zero length will never match with string of non-zero length
					for i in range(1							,      UpperCamelCase__	):
										UpperCAmelCase			:   Dict      =				0

					# since string of zero length will match with pattern where there
					# is at least one * alternatively
					for j in range(1							,      UpperCamelCase__	):
										UpperCAmelCase			:   List[str]      =				dp[0][j - 2] if pattern[j - 1] == "*" else 0

					# now using bottom-up approach to find for all remaining lengths
					for i in range(1							,      UpperCamelCase__	):
										for j in range(1							,      UpperCamelCase__	):
															if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
																				UpperCAmelCase			:   Optional[int]      =				dp[i - 1][j - 1]

															elif pattern[j - 1] == "*":
																				if dp[i][j - 2] == 1:
																									UpperCAmelCase			:   Optional[Any]      =				1
																				elif pattern[j - 2] in (input_string[i - 1], "."):
																									UpperCAmelCase			:   List[str]      =				dp[i - 1][j]
																				else:
																									UpperCAmelCase			:   Optional[int]      =				0
															else:
																				UpperCAmelCase			:   str      =				0

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


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	# inputing the strings
	# input_string = input("input a string :")
	# pattern = input("input a pattern :")

	snake_case_   :   Optional[Any]        =       "aab"
	snake_case_   :   List[Any]        =       "c*a*b"

	# using function to check whether given string matches the given pattern
	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}''')





"""simple docstring"""






def   lowercase_	(    _lowercase       :		list							,      _lowercase       :		int							,      _lowercase       :		int = 0							,      _lowercase       :		int = 0	):




					'''simple docstring'''






					UpperCAmelCase			:   Tuple      =				right or len(_lowercase	) - 1
					if left > right:
										return -1
					elif list_data[left] == key:
										return left
					elif list_data[right] == key:
										return right
					else:
										return search(_lowercase							,      _lowercase							,      left + 1							,      right - 1	)


if __name__ == "__main__":
	import doctest

	doctest.testmod()


