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

Arnab Chakraborty

更新於: 2020年10月12日

434 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習