在Python中查找要更正拼写错误的单词所需更改字符总数的程序

假设我们给出一个城市列表和连接彼此的道路列表。列表’cities’包含巴士依次访问的城市名称。在列表’roads’中，道路按（源，目的地）顺序列出，表示源到目的地有一条单向道路。现在，问题是列表’cities’中的某些城市名称可能拼写错误。我们必须通过改变最少数量的字符来更正这样的拼写错误城市名称。我们将更改的字符数作为输出返回。

因此，如果输入为cities = [“HWH”, “DLI”, “BGL”]，roads = [[“HWH”, “DLI”],[“DLI”, “BCT”], [“BCT”, “HWH”]]，那么输出将为2。

城市中的拼写错误的城市名是’BGL’。正确的名称应为’BCT’。因此，要更正城市中的名称，我们必须更改2个字符。

为了解决这个问题，我们将遵循以下步骤−

• 定义一个diff()函数。这将使用a，b
  • 返回a和b之间字符的总差异
• size := cities的大小
• arr :=一个新的映射
• junctions := roads中每个源城市的一个新集合
• 对于j中的每个交集，执行以下操作：
  • arr[j]:= diff(cities[0],j)
• 对于范围[1，size]中的i，执行以下操作：
  • nxt :=一个新的映射
  • 对于roads中的每个r1、r2，执行以下操作：
    • 如果arr中存在r1，则
    • cost := arr[r1] + diff(cities[i], r2)
    • 如果r2不在nxt中，或者cost<nxt[r2]，则
      • nxt[r2] := cost
  • arr:=nxt
• 返回arr中所有值的最小值

示例

让我们看一下以下实现，以更好地理解−

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