Pythonで文字列をK回以内の移動で別の文字列へ変換できるか判定するプログラム

2つの文字列 s と t が与えられたとき、s を k 回以内の移動で t に変換できるかどうかを判定します。i 回目の移動では、次のいずれかの操作を行えます。

• s 内の任意のインデックス j(1始まり)を選択します。ただし 1 <= j <= len(s) であり、j は過去の移動で一度も選択されていない必要があります。そのうえで、その位置の文字を i 回シフトします。
• 何もせず、そのままにしておきます。

ここで「シフトする」とは、その文字をアルファベット順で次の文字に置き換えることを意味します('z' の場合は 'a' へ折り返します)。したがって「文字を i 回シフトする」とは、この操作を i 回繰り返し適用することです。

たとえば、入力が s = "poput"、t = "vwput"、k = 9 の場合、出力は True になります。これは、i = 6 の移動で 'p' を 'v' に、i = 8 の移動で 'o' を 'w' にそれぞれ変換できるためです。

解法のアプローチ

この問題は、次の手順で解くことができます。

• s と t の長さが一致しない場合は、False を返します。
• count を、0〜25 の各 i について min(1, k - i + 1) + (k - i) // 26 の値を持つ配列として初期化します。これは「ちょうど i 回のシフトを実現できる移動の残り回数」を表します。
• s と t の対応する文字 c1、c2 を順に調べます。
  • c1 と c2 が異なる場合:
    • diff := (ord(c2) - ord(c1) + 26) % 26 を計算します。
    • count[diff] <= 0 ならば False を返します。
    • count[diff] を 1 減らします。
• すべての文字を確認できたら True を返します。

考え方のポイント

ある文字をちょうど diff 回シフトして一致させるには、「移動番号 i を 26 で割った余りが diff に等しい」ような i を使う必要があります。候補となるのは i = diff, diff+26, diff+52, … であり、k 回以内に含まれる個数が min(1, k - diff + 1) + (k - diff) // 26 で求まります。同じ diff が必要な文字同士でこの枠を共有するため、該当する文字のペアごとに 1 つずつ消費していき、足りなくなった時点で変換不可能と判断します。

それでは、実際の実装を見てみましょう。

サンプルコード(Python)

def solve(s, t, k):
    if len(s) != len(t):
        return False
    count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)]
    for c1, c2 in zip(s, t):
        if (c1 != c2):
            diff = (ord(c2) - ord(c1) + 26) % 26
            if count[diff] <= 0:
                return False
            count[diff] -= 1
    return True

s = "poput"
t = "vwput"
k = 9
print(solve(s, t, k))

入力

"poput","vwput",9

出力

True

計算量

時間計算量は O(n)(n は文字列の長さ)、追加で必要な空間計算量は O(1)(サイズ 26 の固定配列のみ)です。文字列の長さに比例して処理できるため、大きな入力にも効率的に対応できます。