找出要更改的字符总数以修复 Python 中拼写错误的单词的程序

假设我们有一个城市列表和一个相互连接的道路列表。列表“城市”包含旅游巴士按顺序访问的城市名称。在“道路”列表中，道路以（源、目的地）顺序列出，这意味着从源到目的地有一条单向道路。现在，存在列表“城市”中的某些城市名称可能拼写错误的问题。我们必须通过更改最少字符数来更正这些拼错的城市名称。我们返回更改的字符数作为输出。

因此，如果输入类似于城市 = ["HWH", "DLI", "BGL"],roads = [["HWH", "DLI"],["DLI", "BCT"], ["BCT" , "HWH"]]，则输出为 2。

城市中拼错的城市名称是“BGL”。正确的名称是“BCT”。因此，在城市中更正名称我们必须更改 2 个字符。

示例

让我们看看以下实现以获得更好的理解 -

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