Pythonで2つの文字列が0または1編集距離離れているかどうかをチェックするプログラム

2つの文字列SとTがあり、それらが編集距離が1か0かどうかを確認する必要があるとします。編集操作は、文字の削除、文字の追加、または文字を別の文字に置き換えることとして定義できます。

したがって、入力がS ="hello"、T ="hallo"の場合、これら2つの文字列の編集距離は1であるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• m：=Sのサイズ、n：=Tのサイズ
• i：=0、j：=0
• count：=0
• if | m --n |> 1、次に
  • Falseを返す
• i
• S[i]がT[j]と同じでない場合、
  • カウントが1と同じ場合、
    • Falseを返す
  • m
  • j：=j + 1
• それ以外の場合、m> nの場合、
  • i：=i + 1
• それ以外の場合、
  • i：=i + 1、j：=j + 1
• count：=count + 1

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, S, T):
      m, n = len(S), len(T)
      i, j = 0, 0
      count = 0
      if abs(m - n) > 1:
         return False
      while i < m and j < n:
         if S[i] != T[j]:
            if count == 1:
               return False
            if m < n:
               j += 1
            elif m > n:
               i += 1
            else:
               i += 1
               j += 1
            count += 1
         else:
            i += 1
            j += 1
      return True
ob = Solution()
S = "hello"
T = "hallo"
print(ob.solve(S, T))

入力

"hello", "hallo"

出力

True