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

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

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

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

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

• 定义一个函数 diff()。这将需要 a、b
  • 返回 a 和 b 之间的字符总差异
• size := 城市大小
• arr := 一个新映射
• junctions := 来自 roads 中每个源城市的新集合
• 对于 junctions 中的每个 j，执行
  • arr[j] := diff(cities[0], j)
• 对于范围从 1 到 size 的 i，执行
  • 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

相关文章

• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?
• 用 Python 编写程序检查我们是否可以从给定的字符串字符中创建 k 个回文?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/