Home Coding Leetcode Hard

⭐️⭐️⭐️

# 題目敘述

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 do not 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”.

# 解題思路

We can create a 2D table dp, where dp[i][j] represents the minimum number of insertions required to make the substring s[i:j+1] a palindrome.

The base case is when i=j , where the substring is already a palindrome and no insertions are needed.

If s[i] == s[j] , then the substring is already a palindrome and we can use the result of dp[i+1][j-1] . Otherwise, we need to insert either a character at index i or j to make them equal, so we take the minimum of dp[i+1][j] and dp[i][j-1] and add 1 to it.

The final answer is stored in dp[0][n-1] , where n is the length of the input string s .

# Solution

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i=n-2; i>=0; i--) {
            for (int j=i+1; j<n; j++) {
                if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1];
                else dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
            }
        }
        return dp[0][n-1];
    }
};
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i=n-1; i>=0; i--) {
            for (int j=i+1; j<n; j++) {
                if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1];
                else dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
            }
        }
        return dp[0][n-1];
    }
}
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n-2, -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] = min(dp[i+1][j], dp[i][j-1]) + 1
        return dp[0][n-1]