'''simple docstring'''

def      UpperCamelCase_						(					snake_case_       :       str						,		snake_case_       :       str      )					->     bool:






 '''simple docstring'''

 __lowerCAmelCase											=						len(snake_case_      ) + 1
 __lowerCAmelCase											=						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.
 __lowerCAmelCase											=						[[0 for i in range(snake_case_      )] for j in range(snake_case_      )]

 # since string of zero length match pattern of zero length
 __lowerCAmelCase											=						1

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

 # since string of zero length will match with pattern where there
 # is at least one * alternatively
 for j in range(1						,		snake_case_      ):
  __lowerCAmelCase											=						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] == ".":
    __lowerCAmelCase											=						dp[i - 1][j - 1]

   elif pattern[j - 1] == "*":
    if dp[i][j - 2] == 1:
     __lowerCAmelCase											=						1
    elif pattern[j - 2] in (input_string[i - 1], "."):
     __lowerCAmelCase											=						dp[i - 1][j]
    else:
     __lowerCAmelCase											=						0
   else:
    __lowerCAmelCase											=						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 :")

 _A			:      Union[str, Any]					      =				'''aab'''
 _A			:      Union[str, 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'''

from __future__ import annotations

from dataclasses import dataclass







@dataclass
class 				_lowercase     :


 '''simple docstring'''






 _SCREAMING_SNAKE_CASE     :       float
 _SCREAMING_SNAKE_CASE     :       TreeNode | None      	=					None
 _SCREAMING_SNAKE_CASE     :       TreeNode | None      	=					None







def      UpperCamelCase_						(					snake_case_       :       TreeNode | None      )					->     bool:






 '''simple docstring'''

 def is_valid_tree(snake_case_       :       TreeNode | None      ) -> bool:
  if node is None:
   return True

  if not isinstance(snake_case_						,		snake_case_      ):
   return False

  try:
   float(node.data      )
  except (TypeError, ValueError):
   return False

  return is_valid_tree(node.left      ) and is_valid_tree(node.right      )

 if not is_valid_tree(snake_case_      ):
  raise ValueError(
      """Each node should be type of TreeNode and data should be float."""      )

 def is_binary_search_tree_recursive_check(
     snake_case_       :       TreeNode | None						,		snake_case_       :       float						,		snake_case_       :       float      ) -> bool:

  if node is None:
   return True

  return (
      left_bound < node.data < right_bound
      and is_binary_search_tree_recursive_check(node.left						,		snake_case_						,		node.data      )
      and is_binary_search_tree_recursive_check(
          node.right						,		node.data						,		snake_case_      )
  )

 return is_binary_search_tree_recursive_check(snake_case_						,		-float("""inf"""      )						,		float("""inf"""      )      )


if __name__ == "__main__":
 import doctest

 doctest.testmod()






