Welcome to Subscribe On Youtube

1312. Minimum Insertion Steps to Make a String Palindrome

Description

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".

 

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Solutions

Solution 1: Depth-First Search + Memoization

We design a function $dfs(i, j)$ to represent the minimum number of operations required to turn the string $s[i..j]$ into a palindrome string. Then the answer is $dfs(0, n - 1)$.

The calculation process of function $dfs(i, j)$ is as follows:

If $i \geq j$, no characters need to be inserted at this time, we directly return $0$.

Otherwise, we determine whether $s[i]$ is equal to $s[j]$. If $s[i]=s[j]$, then we only need to turn $s[i+1..j-1]$ into a palindrome string, then we return $dfs(i + 1, j - 1)$. Otherwise, we can insert a character on the left side of $s[i]$ or on the right side of $s[j]$ that is the same as the other side, then $dfs(i, j) = \min(dfs(i + 1, j), dfs(i, j - 1)) + 1$.

In order to avoid repeated calculations, we can use memoization search, which uses a hash table or array to store the calculated function values.

Finally, we return $dfs(0, n - 1)$.

Time complexity $O(n^2)$, space complexity $O(n^2)$. Where $n$ is the length of the string $s$.

Solution 2

We define $f[i][j]$ to represent the minimum number of operations required to turn the string $s[i..j]$ into a palindrome string. Initially $f[i][j]=0$, the answer is $f[0][n-1]$.

For $f[i][j]$, if $s[i]=s[j]$, then we just need to turn $s[i+1..j-1]$ into a palindrome, hence $f[i][j]=f[i+1][j-1]$. Otherwise, we can insert a character on the left side of $s[i]$ or on the right side of $s[j]$ that is the same as the other side, then $f[i][j]=\min(f[i+1][j],f[i][j-1])+1$.

To sum up, we can get the state transition equation:

\[f[i][j]=\left\{\begin{array}{ll}f[i+1][j-1], & s[i]=s[j]\\ \min(f[i+1][j],f[i][j-1])+1, & s[i]\neq s[j]\end{array}\right.\]

When enumerating, we can have two enumeration methods:

  1. Enumerate $i$ from large to small, and enumerate $j$ from small to large. This ensures that when calculating the state $f[i][j]$, the states $f[i+1][j-1]$ and $f[i][j-1]$ have already been calculated;
  2. Enumerate the interval length $k$ from small to large, and then enumerate the left endpoint of the interval $i$, then you can get the right endpoint $j=i+k-1$. This also ensures that when calculating the larger interval $f[i][j]$, the smaller intervals $f[i+1][j]$ and $f[i][j-1]$ have already been calculated.

Time complexity $O(n^2)$, space complexity $O(n^2)$. Where $n$ is the length of the string $s$.

Similar topics:

Solution 3

This implementation uses dynamic programming. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

  • class Solution {
    private Integer[][] f;
    private String s;

    public int minInsertions(String s) {
        this.s = s;
        int n = s.length();
        f = new Integer[n][n];
        return dfs(0, n - 1);
    }

    private int dfs(int i, int j) {
        if (i >= j) {
            return 0;
        }
        if (f[i][j] != null) {
            return f[i][j];
        }
        int ans = 1 << 30;
        if (s.charAt(i) == s.charAt(j)) {
            ans = dfs(i + 1, j - 1);
        } else {
            ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
        }
        return f[i][j] = ans;
    }
}


// Solution 2
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[0][n - 1];
    }
}



// Solution 3
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i + k - 1 < n; ++i) {
                int j = i + k - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[0][n - 1];
    }
}


  • class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        int f[n][n];
        memset(f, -1, sizeof(f));
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i >= j) {
                return 0;
            }
            if (f[i][j] != -1) {
                return f[i][j];
            }
            int ans = 1 << 30;
            if (s[i] == s[j]) {
                ans = dfs(i + 1, j - 1);
            } else {
                ans = min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
            }
            return f[i][j] = ans;
        };
        return dfs(0, n - 1);
    }
};


// Solution 2
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        int f[n][n];
        memset(f, 0, sizeof(f));
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1];
                } else {
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[0][n - 1];
    }
};



// Solution 3
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        int f[n][n];
        memset(f, 0, sizeof(f));
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i + k - 1 < n; ++i) {
                int j = i + k - 1;
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1];
                } else {
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[0][n - 1];
    }
};


  • class Solution:
    def minInsertions(self, s: str) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= j:
                return 0
            if s[i] == s[j]:
                return dfs(i + 1, j - 1)
            return 1 + min(dfs(i + 1, j), dfs(i, j - 1))

        return dfs(0, len(s) - 1)


# Solution 2
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        f = [[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]:
                    f[i][j] = f[i + 1][j - 1]
                else:
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
        return f[0][-1]



# Solution 3
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for k in range(2, n + 1):
            for i in range(n - k + 1):
                j = i + k - 1
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1]
                else:
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
        return f[0][n - 1]


  • func minInsertions(s string) int {
	n := len(s)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= j {
			return 0
		}
		if f[i][j] != -1 {
			return f[i][j]
		}
		ans := 1 << 30
		if s[i] == s[j] {
			ans = dfs(i+1, j-1)
		} else {
			ans = min(dfs(i+1, j), dfs(i, j-1)) + 1
		}
		f[i][j] = ans
		return ans
	}
	return dfs(0, n-1)
}


// Solution 2
func minInsertions(s string) int {
	n := len(s)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				f[i][j] = f[i+1][j-1]
			} else {
				f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
			}
		}
	}
	return f[0][n-1]
}



// Solution 3
func minInsertions(s string) int {
	n := len(s)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
	}
	for k := 2; k <= n; k++ {
		for i := 0; i+k-1 < n; i++ {
			j := i + k - 1
			if s[i] == s[j] {
				f[i][j] = f[i+1][j-1]
			} else {
				f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
			}
		}
	}
	return f[0][n-1]
}

All Problems

All Solutions