在Python中找到要添加到字符串中使其变为回文的最小字符数

假设我们有一个字符串s，我们必须找到要插入到s后面使其成为回文的最小字符数。

因此，如果输入为s =“mad”，则输出将为2，因为我们可以添加“am”使其变为“madam”。

为了解决这个问题，我们将按照以下步骤操作−

b := 256，m := 10^9 + 7
s:=将s中每个字符的ASCII值减去97所得的列表
r := s的最后一个元素，l := s的第一个元素
n := s的大小
res := n − 1
p := b
对于i in range(n − 2 to 0, 每次减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
返回res

让我们看下面的实现以获得更好的理解−

更多Python相关文章，请阅读：Python 教程

示例

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