Pythonで2つの文字列間の編集距離が1つであるかどうかを確認します

2つの文字列sとtがあるとします。 sとtの間の編集距離が正確に1であるかどうかを確認する必要があります。ここで、2つの文字列間の編集は、これら3つの文字列のいずれかを意味します-

• 文字を挿入
• 文字を削除する
• 文字を置き換える

したがって、入力がs ="hello" t ="heillo"のような場合、tを取得するにはsに1文字を挿入する必要があるため、出力はTrueになります。

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

• if|sのサイズ-tのサイズ|> 1、次に
  • falseを返す
• edit_dist_cnt：=0、i：=0、j：=0
• i
• s[i]がt[j]と同じでない場合、
  • edit_dist_cntが1と同じ場合、
    • falseを返す
  • sのサイズ>tのサイズの場合、
    • i：=i + 1
  • それ以外の場合、sのサイズ
  • j：=j + 1
• それ以外の場合、
  • i：=i + 1、j：=j + 1
• edit_dist_cnt：=edit_dist_cnt + 1

例

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

def solve(s, t):
   if abs(len(s) - len(t)) > 1:
      return false
   edit_dist_cnt = 0
   i = 0
   j = 0
   while i < len(s) and j < len(t):
      if s[i] != t[j]:
         if edit_dist_cnt == 1:
            return false
         if len(s) > len(t):
            i += 1
         elif len(s) < len(t):
            j += 1
         else:
            i += 1
            j += 1
         edit_dist_cnt +=1
      else:
         i += 1
         j += 1
   if i < len(s) or j < len(t):
      edit_dist_cnt += 1
   return edit_dist_cnt == 1
s = "hello"
t = "heillo"
print(solve(s, t))

入力

"hello", "heillo"

出力

True