Pythonで指定されたインデックスに基づいて文字列をシャッフルする方法

文字列 s とインデックスのリスト ind が与えられ、両者は同じ長さであるとします。文字列 s は、位置 i にある文字が最終的な文字列内の ind[i] の位置へ移動するようにシャッフルされます。このとき、シャッフル後の最終的な文字列を求める必要があります。

例えば、入力が s = "ktoalak"、ind = [0,5,1,6,2,4,3] の場合、出力は "kolkata" となります。

解決手順

この問題を解くには、以下の手順に従います。

• fin_str を s と同じサイズのリストとして作成し、0で初期化する

• s 内の各インデックス i と各文字 v に対して、次の操作を行う

  • fin_str[ind[i]] := v と代入する

• fin_str 内のすべての文字を連結し、結果として返す

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(s, ind):
    fin_str = [0] * len(s)
    for i, v in enumerate(s):
        fin_str[ind[i]] = v

    return "".join(fin_str)

s = "ktoalak"
ind = [0,5,1,6,2,4,3]
print(solve(s, ind))

入力

"ktoalak", [0,5,1,6,2,4,3]

出力

kolkata

アルゴリズムのポイント

このアプローチでは、元の文字列を一度だけ走査しながら、各文字を対応するインデックス位置に直接配置していきます。そのため、時間計算量は文字列の長さを n とした場合に O(n)、結果を格納するための追加リストが必要となるため空間計算量も O(n) となります。非常にシンプルでありながら効率的な手法です。