程序检查在Python中进行字符串回文所需的最少字符数

假设我们有一个字符串s，我们必须找到需要插入的最少字符数，以便该字符串成为回文。

因此，如果输入类似于s =“ mad”，则输出将为2，因为我们可以插入“ am”来获取“ madam”。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个功能dp()。这需要我，j

• 如果i> = j，则

• 返回0

• 如果s [i]与s [j]相同，则

• 返回dp（i + 1，j-1）

• 除此以外，

• 返回dp（i + 1，j）和dp(i,j-1)+ 1的最小值

• 在主要方法中，执行以下操作

• 返回dp（0，s的大小-1）

让我们看下面的实现以更好地理解-

示例

class Solution:
   def solve(self, s):
      def dp(i, j):
         if i >= j:
            return 0
         if s[i] == s[j]:
            return dp(i + 1, j - 1)
         else:
            return min(dp(i + 1, j), dp(i, j - 1)) + 1
      return dp(0, len(s) - 1)
ob = Solution()s = "mad"
print(ob.solve(s))

输入值

s = "mad"

输出结果

2