Pythonでスペルミスのある単語を修正するために変更する文字の総数を見つけるプログラム

都市のリストと相互に接続する道路のリストが与えられたとします。リスト「都市」には、ツアーバスが順番に訪れる都市の名前が含まれています。リスト「道路」では、道路は（ソース、宛先）の順序でリストされています。これは、ソースから宛先への片道道路があることを意味します。現在、リスト「都市」の一部の都市名のつづりが間違っている可能性があるという問題があります。最小文字数を変更して、このようなスペルミスのある都市名を修正する必要があります。変更された文字数を出力として返します。

したがって、入力が都市=["HWH"、 "DLI"、 "BGL"]の場合、道路=[["HWH"、 "DLI"]、["DLI"、 "BCT"]、["BCT" 、"HWH"]]の場合、出力は2になります。

都市のスペルミスのある都市名は「BGL」です。正しい名前は「BCT」です。したがって、都市の名前を修正しすぎると、2文字を変更する必要があります。

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

• 関数diff（）を定義します。これにはa、b
  がかかります
  • aとbの文字の合計差を返します
• サイズ：=都市のサイズ
• arr：=新しい地図
• ジャンクション：=道路の各ソース都市からの新しいセット
• ジャンクション内のjごとに、
  • arr [j]：=diff（cities [0]、j）
• 1からサイズの範囲のiの場合は、
  • nxt：=新しいマップ
  • 道路のr1、r2ごとに、
    • r1がarrに存在する場合、
      • コスト：=arr [r1] + diff（cities [i]、r2）
      • r2がnxtに存在しないか、コストが
      • nxt [r2]：=コスト
• arr：=nxt

例

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

def diff(a, b):
   return sum(x != y for x, y in zip(a, b))

def solve(cities, roads):
   size = len(cities)
   arr = dict()
   junctions = set(r[0] for r in roads)
   for j in junctions:
      arr[j] = diff(cities[0], j)
   for i in range(1, size):
      nxt = dict()
      for r1, r2 in roads:
         if r1 in arr:
            cost = arr[r1] + diff(cities[i], r2)
            if r2 not in nxt or cost < nxt[r2]:
               nxt[r2] = cost
      arr = nxt
   return min(arr.values())

print(solve(["HWH", "DLI", "BGL"], [["HWH", "DLI"],["DLI", "BCT"],
["BCT", "HWH"]]))

入力

["HWH", "DLI", "BGL"], [["HWH", "DLI"],["DLI", "BCT"], ["BCT",
"HWH"]]

出力

2