【Python】文字を時計回りにシフトして文字列を変換できるか判定するプログラム

問題概要

2つの文字列 p と q、および数値 r が与えられたとき、p に含まれる各文字をアルファベット順に時計回りへ最大 r 回までシフトすることで、p を q に変換できるかどうかを判定するプログラムを作成します。

例えば、「c」は時計回りに2回シフトすると「e」になります（c → d → e）。

入力例と出力例

入力が p = "abc"、q = "ccc"、r = 3 の場合を考えてみましょう。

• 「a」を時計回りに2回シフトすると「c」になる
• 「b」を時計回りに1回シフトすると「c」になる

合計のシフト回数が3回で、許容される上限 r = 3 以内に収まるため、出力は True となります。

解法のアプローチ

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

1. まず、文字列 a と b の長さが異なる場合は変換不可能なので False を返します。
2. k が 0 であり、かつ a と b が一致しない場合も False を返します。
3. 必要なシフト回数の合計を格納する変数 su を 0 で初期化します。
4. 各文字について以下を繰り返します。
   • v = b[i] のASCIIコード − a[i] のASCIIコード を計算します。
   • v が 0 以上であれば、su にそのまま v を加算します。
   • v が負の場合（例：「z」から「a」への変換など）、アルファベット1周分の 26 を加算して補正してから su に足します。これにより、折り返しを含めた実際のシフト回数が正しく求まります。
   • 途中で su が k を超えたら、それ以上計算しても無意味なので即座に False を返します（早期終了による効率化）。
5. ループを最後まで抜けられれば、すべての文字が必要回数以内で変換できるため True を返します。

このアルゴリズムの計算量は文字列の長さを n とすると O(n) で、非常に効率的です。

実装例

理解を深めるために、以下の Python コードを見てみましょう。

class Solution:
    def solve(self, a, b, k):
        if len(a) != len(b):
            return False
        if k == 0 and a != b:
            return False
        su = 0
        for i in range(len(a)):
            v = ord(b[i]) - ord(a[i])
            if v >= 0:
                su += v
            else:
                su += v + 26
            if su > k:
                return False
        return True

ob = Solution()
print(ob.solve("abc", "ccc", 3))

入力

"abc", "ccc", 3

出力

True

ポイント解説

• ord() 関数：Pythonの組み込み関数で、文字をASCIIコード（整数）に変換します。これにより文字同士の差分を数値として計算できます。
• +26 の補正：アルファベットは26文字で循環しているため、負の差分が出た場合は26を加えることで「z → a」のような折り返しを含んだ正しいシフト回数が得られます。
• 早期リターン：合計シフト回数が上限 k を超えた時点で False を返すことで、無駄な計算を省いています。