Pythonを使用してKムーブで文字列を変換できるかどうかを確認するプログラム

2つの文字列sとtがあるとすると、sをk移動以下でtに変換できるかどうかを確認する必要があります。どちらの動きでも、これらの操作を実行できます。

• s内の任意のインデックスj（1から始まる）を選択して、1 <=j <=sのサイズとjが前の移動で選択されていないようにし、そのインデックスiの文字を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について（最小1および（k --i + 1 +（k --i）/ 26））を保持する配列

• sからのc1とtからのc2の各文字について、実行します

  • c1がc2と同じでない場合、

    • diff：=（c2のASCII-c1のASCII + 26）mod 26

    • count [diff] <=0の場合、

      • Falseを返す

    • count [diff]：=count [diff]-1

• Trueを返す

理解を深めるために、次の実装を見てみましょう

例

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