程序检查在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