Python 程序：检查将字符串转换为回文串所需的最小字符数

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

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

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

  • 定义一个函数 dp()。它将接收 i、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

更新于: 2020年10月12日

434 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告