
from timeit import timeit

snake_case :		List[str]							      =  {
    "MALAYALAM": True,
    "String": False,
    "rotor": True,
    "level": True,
    "A": True,
    "BB": True,
    "ABC": False,
    "amanaplanacanalpanama": True,  # "a man a plan a canal panama"
}
# Ensure our test data is valid
assert all((key == key[::-1]) is value for key, value in test_data.items())






def   lowerCAmelCase_						(					_snake_case      :  str   )				->		bool:







	'''simple docstring'''


	__magic_name__		:		Union[str, Any]	   =     0
	__magic_name__		:		Union[str, Any]	   =     len(_snake_case   ) - 1
	while start_i < end_i:
		if s[start_i] == s[end_i]:
			start_i += 1
			end_i -= 1
		else:
			return False
	return True






def   lowerCAmelCase_						(					_snake_case      :  str   )				->		bool:







	'''simple docstring'''


	__magic_name__		:		Dict	   =     len(_snake_case   ) // 2
	__magic_name__		:		Tuple	   =     len(_snake_case   )

	# We need to traverse till half of the length of string
	# as we can get access of the i'th last element from
	# i'th index.
	# eg: [0,1,2,3,4,5] => 4th index can be accessed
	# with the help of 1st index (i==n-i-1)
	# where n is length of string
	return all(s[i] == s[n - i - 1] for i in range(_snake_case   )   )






def   lowerCAmelCase_						(					_snake_case      :  str   )				->		bool:







	'''simple docstring'''


	if len(_snake_case   ) <= 2:
		return True
	if s[0] == s[len(_snake_case   ) - 1]:
		return is_palindrome_recursive(s[1:-1]   )
	else:
		return False






def   lowerCAmelCase_						(					_snake_case      :  str   )				->		bool:







	'''simple docstring'''


	return s == s[::-1]






def   lowerCAmelCase_						(					_snake_case      :  str   )				->		None:







	'''simple docstring'''


	__magic_name__		:		Dict	   =     F'''all({name}(key) is value for key, value in test_data.items())'''
	__magic_name__		:		Dict	   =     F'''from __main__ import test_data, {name}'''
	__magic_name__		:		Optional[int]	   =     500000
	__magic_name__		:		Dict	   =     timeit(stmt=_snake_case      ,   setup=_snake_case      ,   number=_snake_case   )
	print(F'''{name:<35} finished {number:,} runs in {result:.5f} seconds'''   )


if __name__ == "__main__":
				for key, value in test_data.items():
								assert is_palindrome(key) is is_palindrome_recursive(key)
								assert is_palindrome(key) is is_palindrome_slice(key)
								print(F"{key:21} {value}")
				print("a man a plan a canal panama")

				# finished 500,000 runs in 0.46793 seconds
				benchmark_function("is_palindrome_slice")
				# finished 500,000 runs in 0.85234 seconds
				benchmark_function("is_palindrome")
				# finished 500,000 runs in 1.32028 seconds
				benchmark_function("is_palindrome_recursive")
				# finished 500,000 runs in 2.08679 seconds
				benchmark_function("is_palindrome_traversal")


def   lowerCAmelCase_						(					_snake_case      :  str      ,   _snake_case      :  str   )				->		bool:







	'''simple docstring'''


	__magic_name__		:		Union[str, Any]	   =     len(_snake_case   ) + 1
	__magic_name__		:		List[str]	   =     len(_snake_case   ) + 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.
	__magic_name__		:		str	   =     [[0 for i in range(_snake_case   )] for j in range(_snake_case   )]

	# since string of zero length match pattern of zero length
	__magic_name__		:		Optional[int]	   =     1

	# since pattern of zero length will never match with string of non-zero length
	for i in range(1      ,   _snake_case   ):
		__magic_name__		:		Optional[int]	   =     0

	# since string of zero length will match with pattern where there
	# is at least one * alternatively
	for j in range(1      ,   _snake_case   ):
		__magic_name__		:		Union[str, Any]	   =     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      ,   _snake_case   ):
		for j in range(1      ,   _snake_case   ):
			if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
				__magic_name__		:		Optional[int]	   =     dp[i - 1][j - 1]

			elif pattern[j - 1] == "*":
				if dp[i][j - 2] == 1:
					__magic_name__		:		Optional[Any]	   =     1
				elif pattern[j - 2] in (input_string[i - 1], "."):
					__magic_name__		:		List[Any]	   =     dp[i - 1][j]
				else:
					__magic_name__		:		Union[str, Any]	   =     0
			else:
				__magic_name__		:		Dict	   =     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[str]							      =  "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}")
