Pythonでリストの最後のインデックスに到達する最小ステップ数を求めるプログラム

問題の概要

数値のリスト nums が与えられ、現在は nums[0] の位置にいるものとします。各ステップでは、現在のインデックス i から以下のいずれかに移動できます。

• i + 1（一つ右隣へ移動）
• i - 1（一つ左隣へ移動）
• j（nums[i] == nums[j] を満たす任意のインデックス j へジャンプ）

このとき、リストの最後のインデックスに到達するまでに必要な最小ステップ数を求めます。

例

入力が nums = [4, 8, 8, 5, 4, 6, 5] の場合、出力は 3 になります。その理由は以下の通りです。

• インデックス 0 と インデックス 4 はどちらも値が 4 なので、インデックス 0 から インデックス 4 へ直接ジャンプできます。
• 次に、インデックス 4 から インデックス 3 へ一つ戻ります。
• 最後に、インデックス 3 と インデックス 6 はどちらも値が 5 なので、インデックス 3 から インデックス 6 へジャンプできます。

合計 3 ステップで最後のインデックスに到達できます。

解決のアプローチ

この問題は、BFS（幅優先探索）を用いて効率的に解くことができます。BFS は最短経路を求めるのに適しており、各ノード（インデックス）をレベルごとに探索することで、最小ステップ数が保証されます。手順は以下の通りです。

• pos := 空のマップ（辞書）を作成し、同じ値を持つすべてのインデックスを値ごとにグループ化して登録します。
• n := リスト nums のサイズとします。
• visited := サイズ n のリストを作成し、すべて False で初期化します。
• visited[0] := True とし、キュー q に開始位置を表すペア (0, 0)（インデックス, ステップ数）を追加します。
• キュー q が空でない間、以下を繰り返します。
  • (u, d) := キューの先頭要素を取り出します。
  • u が n - 1 と等しければ、d（最小ステップ数）を返します。
  • pos[nums[u]] に含まれる各 v および [u - 1, u + 1] の各 v について、0 <= v < n かつ visited[v] が False であれば、visited[v] を True にし、ペア (v, d + 1) をキューの末尾に追加します。
  • 同じ値への不要な再訪問を防ぐため、処理済みの pos[nums[u]] を削除します。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

class Solution:
    def solve(self, nums):
        from collections import defaultdict, deque
        pos = defaultdict(list)
        for i, n in enumerate(nums):
            pos[n].append(i)
        q = deque([(0, 0)])
        n = len(nums)
        visited = [False] * n
        visited[0] = True
        while q:
            u, d = q.popleft()
            if u == n - 1:
                return d
            for v in pos[nums[u]] + [u - 1, u + 1]:
                if 0 <= v < n and not visited[v]:
                    visited[v] = True
                    q.append((v, d + 1))
            del pos[nums[u]]

ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))

入力

[4, 8, 8, 5, 4, 6, 5]

出力

3

計算量の分析

時間計算量： O(n) ― 各インデックスは最大一度しかキューに追加されず、同じ値のグループも削除されるため二度と走査されません。
空間計算量： O(n) ― 値ごとのインデックスマップ、visited 配列、キューのために追加のメモリが必要です。