Minimum Insertions to Make Palindrome
This program finds minimum insertions to make string palindrome.
Problem Statement
Write a Java program to find minimum insertions to make "abcda" palindrome.
Source Code
| 1 | public class MinInsertionsPalindrome { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Min Insertions Palindrome"); |
| 4 | String str="abcda"; |
| 5 | int n=str.length(); |
| 6 | int[][] dp=new int[n][n]; |
| 7 | for(int gap=1;gap<n;gap++){ |
| 8 | for(int i=0,j=gap;j<n;i++,j++){ |
| 9 | if(str.charAt(i)==str.charAt(j)) dp[i][j]=dp[i+1][j-1]; |
| 10 | else dp[i][j]=1+Math.min(dp[i+1][j],dp[i][j-1]); |
| 11 | } |
| 12 | } |
| 13 | System.out.println("Minimum insertions = "+dp[0][n-1]); |
| 14 | } |
| 15 | } |
Program Output
Eduinq Min Insertions Palindrome Minimum insertions = 2
Explanation
A DP table is filled by increasing gap size between compared positions, adding no insertions when the end characters match and otherwise taking the minimum of two possible insertion choices, together finding the minimum insertions required to make the string a palindrome.