Pythonで回文にするために追加する文字の最小数を見つけるプログラム

文字列sがあるとすると、sの後に挿入する文字の最小数を見つけて、回文にする必要があります。

したがって、入力がs ="mad"の場合、出力は2になります。これは、"am"を追加して"madam"にすることができるためです。

これを解決するには、次の手順に従います-

• b：=256、m：=10 ^ 9 + 7

• s：=sの各iについて（iのASCII）−97の差をとったリスト

• r：=sの最後の要素、l：=sの最後の要素

• n：=sのサイズ

• res：=n − 1

• p：=b

• n − 2から0の範囲のiの場合、1ずつ減らします。

  • r：=r + s [i] * p、r：=r mod m

  • l：=l * b、l：=l + s [i]

  • l：=l mod m

  • p：=p * b、p：=p mod m

  • lがrと同じ場合、

    • res：=i

• 解像度を返す

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

例

class Solution:
   def solve(self, s):
      b = 256
      m = 10 ** 9 + 7
      s = list(ord(i) − 97 for i in s)
      r = l = s[−1]
      n = len(s)
      res = n − 1
      p = b
      for i in range(n − 2, −1, −1):
         r += s[i] * p
         r %= m
         l *= b
         l += s[i]
         l %= m
         p *= b
         p %= m
         if l == r:
            res = i
      return res
ob = Solution()
s = "mad"
print(ob.solve(s))

入力

"mad"

出力

2