資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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
- 如果 r1 存在於 arr 中，則執行以下操作：
- 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 次檢視
廣告