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
DP table compares characters at ends. - Insertions counted to form palindrome. - Together finds minimum insertions. Conclusion: Shows how to find minimum insertions to make string palindrome.