https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
Given a string s. In one step you can insert any character at any index of the string.
Return the minimum number of steps to make s palindrome.
A Palindrome String is one that reads the same backward as well as forward.
Example 1:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.
Example 2:
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".
Example 3:
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".
Example 4:
Input: s = "g"
Output: 0
Example 5:
Input: s = "no"
Output: 1
-
Recurrence with memo:
Ins(i, j): number of chars that need to be inserted in s[i..j] to make it a palindrome.
Base cases (substrings of length 1 and 2):
Ins(i, i) = 0 (substring of length 1, they are all palindrome)
Ins(i, i+1) = 0 if s[i] == s[i+1], else 1 (substrings of length 2)
General cases (substrings of length >= 3):
Ins(i, j) = Ins(i+1, j-1) if s[i] == s[j], else Ins(i, j) = min(1 + Ins(i+1, j), 1 + Ins(i, j+1))
Goal:
Ins(0, n-1) (the entire s)
-
二维DP，建立数组，button-up求解
dp[0][n-1].
class Solution(object):
def minInsertions(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dp = [[0] * n for _ in range(n))]
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]