Chương trình tìm số ký tự tối thiểu được thêm vào để biến nó thành palindrome trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số ký tự tối thiểu được chèn vào sau s để biến nó thành palindrome.

Vì vậy, nếu đầu vào là s =​​"mad", thì đầu ra sẽ là 2, vì chúng ta có thể thêm "am" để biến nó thành "madam".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• b:=256, m:=10 ^ 9 + 7

• s:=một danh sách bằng cách lấy hiệu (ASCII của i) - 97 cho mỗi i trong s

• r:=phần tử cuối cùng của s, l:=phần tử cuối cùng của s

• n:=kích thước của s

• res:=n - 1

• p:=b

• đối với tôi trong phạm vi n - 2 đến 0, giảm 1, thực hiện

  • 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

  • nếu l giống với r thì

    • res:=i

• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

"mad"

Đầu ra

2