Pythonでスペルミスのある単語を修正するために変更する文字の総数を見つけるプログラム

問題の概要

都市のリストと、それらをつなぐ道路のリストが与えられるとします。「cities」リストには、観光バスが訪問順に立ち寄る都市名が格納されています。一方「roads」リストには、(出発地, 目的地) の形式で一方通行の道路が列挙されています。

ここで問題になるのが、「cities」リストの中にスペルミスのある都市名が含まれている可能性があるという点です。私たちのタスクは、これらの誤った都市名を最小限の文字変更で正しい名前に修正し、その変更した文字数を出力として返すことです。

入力例

cities = ["HWH", "DLI", "BGL"]
roads = [["HWH", "DLI"], ["DLI", "BCT"], ["BCT", "HWH"]]

この場合、出力は 2 になります。

理由を見てみましょう。「cities」の中でスペルミスがあるのは「BGL」です。道路リストから判断すると、正しい都市名は「BCT」であることがわかります。「BGL」を「BCT」に直すには、2文字(2番目と3番目の文字)を変更する必要があります。

解決のアプローチ

この問題は、動的計画法(DP)の考え方を使って効率的に解くことができます。各ステップで、それまでの経路のコスト(文字変更数)を記録しながら、最終的に最小コストを求めます。

アルゴリズムの手順

• diff() 関数を定義します。引数 a, b を受け取り、2つの文字列間で異なる文字の総数を返します。
• 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 内のすべての値の最小値を返します。

Pythonでの実装例

それでは、上記のアルゴリズムを実際のPythonコードで確認してみましょう。

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

コードのポイント

• diff() 関数:zip() を使って2つの文字列を対応する位置ごとに比較し、異なる文字の個数を合計しています。シンプルながら強力な実装です。
• DPテーブルの更新:各ステップで新しい辞書 nxt を作成することで、前のステップの状態を汚染せずに処理を進められます。
• 最小コストの保持:同じ目的地 r2 に複数の経路がある場合、より小さいコストだけを残すことで、常に最適な解を追跡できます。

このように、グラフ構造と文字列比較を組み合わせた問題でも、動的計画法を活用すれば効率的に最小の文字変更数を求めることができます。