





class 							__lowercase       :







	'''simple docstring'''

	def __init__(self )							->							Optional[int]:







				'''simple docstring'''





				__lowercase										=							''''''
				__lowercase										=							''''''
				__lowercase										=							[]


	def 						_UpperCAmelCase     (self     ,_lowerCamelCase     ,_lowerCamelCase )							->							int:







				'''simple docstring'''





				if m == -1:
							return n + 1
				elif n == -1:
							return m + 1
				elif self.dp[m][n] > -1:
							return self.dp[m][n]
				else:
							if self.worda[m] == self.worda[n]:
										__lowercase										=							self.__min_dist_top_down_dp(m - 1     ,n - 1 )
							else:
										__lowercase										=							self.__min_dist_top_down_dp(_lowerCamelCase     ,n - 1 )
										__lowercase										=							self.__min_dist_top_down_dp(m - 1     ,_lowerCamelCase )
										__lowercase										=							self.__min_dist_top_down_dp(m - 1     ,n - 1 )
										__lowercase										=							1 + min(_lowerCamelCase     ,_lowerCamelCase     ,_lowerCamelCase )

							return self.dp[m][n]


	def 						_UpperCAmelCase     (self     ,_lowerCamelCase     ,_lowerCamelCase )							->							int:







				'''simple docstring'''





				__lowercase										=							worda
				__lowercase										=							worda
				__lowercase										=							[[-1 for _ in range(len(_lowerCamelCase ) )] for _ in range(len(_lowerCamelCase ) )]

				return self.__min_dist_top_down_dp(len(_lowerCamelCase ) - 1     ,len(_lowerCamelCase ) - 1 )


	def 						_UpperCAmelCase     (self     ,_lowerCamelCase     ,_lowerCamelCase )							->							int:







				'''simple docstring'''





				__lowercase										=							worda
				__lowercase										=							worda
				__lowercase										=							len(_lowerCamelCase )
				__lowercase										=							len(_lowerCamelCase )
				__lowercase										=							[[0 for _ in range(n + 1 )] for _ in range(m + 1 )]

				for i in range(m + 1 ):
							for j in range(n + 1 ):
										if i == 0:  # first string is empty
													__lowercase										=							j
										elif j == 0:  # second string is empty
													__lowercase										=							i
										elif worda[i - 1] == worda[j - 1]:  # last characters are equal
													__lowercase										=							self.dp[i - 1][j - 1]
										else:
													__lowercase										=							self.dp[i][j - 1]
													__lowercase										=							self.dp[i - 1][j]
													__lowercase										=							self.dp[i - 1][j - 1]
													__lowercase										=							1 + min(_lowerCamelCase     ,_lowerCamelCase     ,_lowerCamelCase )
				return self.dp[m][n]


if __name__ == "__main__":
	_SCREAMING_SNAKE_CASE					=    EditDistance()

	print('''****************** Testing Edit Distance DP Algorithm ******************''')
	print()

	_SCREAMING_SNAKE_CASE					=    input('''Enter the first string: ''').strip()
	_SCREAMING_SNAKE_CASE					=    input('''Enter the second string: ''').strip()

	print()
	print(f'''The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}''')
	print(f'''The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}''')
	print()
	print('''*************** End of Testing Edit Distance DP Algorithm ***************''')












'''simple docstring'''



from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


_SCREAMING_SNAKE_CASE					=    {
    '''configuration_clipseg''': [
        '''CLIPSEG_PRETRAINED_CONFIG_ARCHIVE_MAP''',
        '''CLIPSegConfig''',
        '''CLIPSegTextConfig''',
        '''CLIPSegVisionConfig''',
    ],
    '''processing_clipseg''': ['''CLIPSegProcessor'''],
}

try:
	if not is_torch_available():
		raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
	pass
else:
	_SCREAMING_SNAKE_CASE					=    [
	    '''CLIPSEG_PRETRAINED_MODEL_ARCHIVE_LIST''',
	    '''CLIPSegModel''',
	    '''CLIPSegPreTrainedModel''',
	    '''CLIPSegTextModel''',
	    '''CLIPSegVisionModel''',
	    '''CLIPSegForImageSegmentation''',
	]

if TYPE_CHECKING:
	from .configuration_clipseg import (
	    CLIPSEG_PRETRAINED_CONFIG_ARCHIVE_MAP,
	    CLIPSegConfig,
	    CLIPSegTextConfig,
	    CLIPSegVisionConfig,
	)
	from .processing_clipseg import CLIPSegProcessor

	try:
		if not is_torch_available():
			raise OptionalDependencyNotAvailable()
	except OptionalDependencyNotAvailable:
		pass
	else:
		from .modeling_clipseg import (
		    CLIPSEG_PRETRAINED_MODEL_ARCHIVE_LIST,
		    CLIPSegForImageSegmentation,
		    CLIPSegModel,
		    CLIPSegPreTrainedModel,
		    CLIPSegTextModel,
		    CLIPSegVisionModel,
		)

else:
	import sys

	_SCREAMING_SNAKE_CASE					=    _LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)





