





"""simple docstring"""





from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_tf_available,
    is_tokenizers_available,
    is_torch_available,
)


SCREAMING_SNAKE_CASE__   =  {
    "configuration_electra": ["ELECTRA_PRETRAINED_CONFIG_ARCHIVE_MAP", "ElectraConfig", "ElectraOnnxConfig"],
    "tokenization_electra": ["ElectraTokenizer"],
}

try:
       if not is_tokenizers_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       SCREAMING_SNAKE_CASE__   =  ["ElectraTokenizerFast"]

try:
       if not is_torch_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       SCREAMING_SNAKE_CASE__   =  [
           "ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST",
           "ElectraForCausalLM",
           "ElectraForMaskedLM",
           "ElectraForMultipleChoice",
           "ElectraForPreTraining",
           "ElectraForQuestionAnswering",
           "ElectraForSequenceClassification",
           "ElectraForTokenClassification",
           "ElectraModel",
           "ElectraPreTrainedModel",
           "load_tf_weights_in_electra",
       ]

try:
       if not is_tf_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       SCREAMING_SNAKE_CASE__   =  [
           "TF_ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST",
           "TFElectraForMaskedLM",
           "TFElectraForMultipleChoice",
           "TFElectraForPreTraining",
           "TFElectraForQuestionAnswering",
           "TFElectraForSequenceClassification",
           "TFElectraForTokenClassification",
           "TFElectraModel",
           "TFElectraPreTrainedModel",
       ]

try:
       if not is_flax_available():
              raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
       pass
else:
       SCREAMING_SNAKE_CASE__   =  [
           "FlaxElectraForCausalLM",
           "FlaxElectraForMaskedLM",
           "FlaxElectraForMultipleChoice",
           "FlaxElectraForPreTraining",
           "FlaxElectraForQuestionAnswering",
           "FlaxElectraForSequenceClassification",
           "FlaxElectraForTokenClassification",
           "FlaxElectraModel",
           "FlaxElectraPreTrainedModel",
       ]


if TYPE_CHECKING:
       from .configuration_electra import ELECTRA_PRETRAINED_CONFIG_ARCHIVE_MAP, ElectraConfig, ElectraOnnxConfig
       from .tokenization_electra import ElectraTokenizer

       try:
              if not is_tokenizers_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .tokenization_electra_fast import ElectraTokenizerFast

       try:
              if not is_torch_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_electra import (
                  ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST,
                  ElectraForCausalLM,
                  ElectraForMaskedLM,
                  ElectraForMultipleChoice,
                  ElectraForPreTraining,
                  ElectraForQuestionAnswering,
                  ElectraForSequenceClassification,
                  ElectraForTokenClassification,
                  ElectraModel,
                  ElectraPreTrainedModel,
                  load_tf_weights_in_electra,
              )

       try:
              if not is_tf_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_tf_electra import (
                  TF_ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST,
                  TFElectraForMaskedLM,
                  TFElectraForMultipleChoice,
                  TFElectraForPreTraining,
                  TFElectraForQuestionAnswering,
                  TFElectraForSequenceClassification,
                  TFElectraForTokenClassification,
                  TFElectraModel,
                  TFElectraPreTrainedModel,
              )

       try:
              if not is_flax_available():
                     raise OptionalDependencyNotAvailable()
       except OptionalDependencyNotAvailable:
              pass
       else:
              from .modeling_flax_electra import (
                  FlaxElectraForCausalLM,
                  FlaxElectraForMaskedLM,
                  FlaxElectraForMultipleChoice,
                  FlaxElectraForPreTraining,
                  FlaxElectraForQuestionAnswering,
                  FlaxElectraForSequenceClassification,
                  FlaxElectraForTokenClassification,
                  FlaxElectraModel,
                  FlaxElectraPreTrainedModel,
              )

else:
       import sys

       SCREAMING_SNAKE_CASE__   =  _LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)













"""simple docstring"""





class 						lowercase   :





      def __init__(			self					)						->	Any:
            lowerCAmelCase    		=			""""""
            lowerCAmelCase    		=			""""""
            lowerCAmelCase    		=			[]





      def        _snake_case     (			self ,		lowercase ,		lowercase					)						->	int:
            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]:
                        lowerCAmelCase    		=			self.__min_dist_top_down_dp(m - 1 ,		n - 1					)
                  else:
                        lowerCAmelCase    		=			self.__min_dist_top_down_dp(lowercase ,		n - 1					)
                        lowerCAmelCase    		=			self.__min_dist_top_down_dp(m - 1 ,		lowercase					)
                        lowerCAmelCase    		=			self.__min_dist_top_down_dp(m - 1 ,		n - 1					)
                        lowerCAmelCase    		=			1 + min(lowercase ,		lowercase ,		lowercase					)

                  return self.dp[m][n]





      def        _snake_case     (			self ,		lowercase ,		lowercase					)						->	int:
            lowerCAmelCase    		=			worda
            lowerCAmelCase    		=			worda
            lowerCAmelCase    		=			[[-1 for _ in range(len(lowercase					)					)] for _ in range(len(lowercase					)					)]

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





      def        _snake_case     (			self ,		lowercase ,		lowercase					)						->	int:
            lowerCAmelCase    		=			worda
            lowerCAmelCase    		=			worda
            lowerCAmelCase    		=			len(lowercase					)
            lowerCAmelCase    		=			len(lowercase					)
            lowerCAmelCase    		=			[[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
                              lowerCAmelCase    		=			j
                        elif j == 0:  # second string is empty
                              lowerCAmelCase    		=			i
                        elif worda[i - 1] == worda[j - 1]:  # last characters are equal
                              lowerCAmelCase    		=			self.dp[i - 1][j - 1]
                        else:
                              lowerCAmelCase    		=			self.dp[i][j - 1]
                              lowerCAmelCase    		=			self.dp[i - 1][j]
                              lowerCAmelCase    		=			self.dp[i - 1][j - 1]
                              lowerCAmelCase    		=			1 + min(lowercase ,		lowercase ,		lowercase					)
            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 ***************")






