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

假设我们给定一个城市列表和一个连接彼此的道路列表。列表'cities'包含旅游巴士按顺序访问的城市名称。在列表'roads'中，道路按（起点，终点）顺序列出，这意味着从起点到终点有一条单向道路。现在，问题是列表'cities'中的一些城市名称可能拼写错误。我们必须通过更改最少的字符数来纠正此类拼写错误的城市名称。我们返回更改的字符数作为输出。

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

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

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

  • 定义一个函数 diff()。这将接收 a、b
    • 返回 a 和 b 之间字符的总差异
  • size := cities 的大小
  • arr := 一个新的映射
  • junctions := 从 roads 中每个起点城市生成的一个新集合
  • 对于 junctions 中的每个 j，执行以下操作：
    • arr[j] := diff(cities[0], j)
  • 对于 i 从 1 到 size 的范围，执行以下操作：
    • nxt := 一个新的映射
    • 对于 roads 中的每个 r1、r2，执行以下操作：
      • 如果 r1 存在于 arr 中，则执行以下操作：
        • 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

更新于： 2021年10月19日

110 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告