用 Python 编写程序检查构成回文字符串所需的最少字符数

pythonserver side programmingprogramming更新于 2026/1/24 15:40:17

假设我们有一个字符串 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))